{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Shopping Offers"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #bit-manipulation #memoization #array #dynamic-programming #backtracking #bitmask"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #位运算 #记忆化搜索 #数组 #动态规划 #回溯 #状态压缩"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: shoppingOffers"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #大礼包"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>在 LeetCode 商店中， 有 <code>n</code> 件在售的物品。每件物品都有对应的价格。然而，也有一些大礼包，每个大礼包以优惠的价格捆绑销售一组物品。</p>\n",
    "\n",
    "<p>给你一个整数数组 <code>price</code> 表示物品价格，其中 <code>price[i]</code> 是第 <code>i</code> 件物品的价格。另有一个整数数组 <code>needs</code> 表示购物清单，其中 <code>needs[i]</code> 是需要购买第 <code>i</code> 件物品的数量。</p>\n",
    "\n",
    "<p>还有一个数组 <code>special</code> 表示大礼包，<code>special[i]</code> 的长度为 <code>n + 1</code> ，其中 <code>special[i][j]</code> 表示第 <code>i</code> 个大礼包中内含第 <code>j</code> 件物品的数量，且 <code>special[i][n]</code> （也就是数组中的最后一个整数）为第 <code>i</code> 个大礼包的价格。</p>\n",
    "\n",
    "<p>返回<strong> 确切 </strong>满足购物清单所需花费的最低价格，你可以充分利用大礼包的优惠活动。你不能购买超出购物清单指定数量的物品，即使那样会降低整体价格。任意大礼包可无限次购买。</p>\n",
    "\n",
    "<p> </p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>price = [2,5], special = [[3,0,5],[1,2,10]], needs = [3,2]\n",
    "<strong>输出：</strong>14\n",
    "<strong>解释：</strong>有 A 和 B 两种物品，价格分别为 ¥2 和 ¥5 。 \n",
    "大礼包 1 ，你可以以 ¥5 的价格购买 3A 和 0B 。 \n",
    "大礼包 2 ，你可以以 ¥10 的价格购买 1A 和 2B 。 \n",
    "需要购买 3 个 A 和 2 个 B ， 所以付 ¥10 购买 1A 和 2B（大礼包 2），以及 ¥4 购买 2A 。</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>price = [2,3,4], special = [[1,1,0,4],[2,2,1,9]], needs = [1,2,1]\n",
    "<strong>输出：</strong>11\n",
    "<strong>解释：</strong>A ，B ，C 的价格分别为 ¥2 ，¥3 ，¥4 。\n",
    "可以用 ¥4 购买 1A 和 1B ，也可以用 ¥9 购买 2A ，2B 和 1C 。 \n",
    "需要买 1A ，2B 和 1C ，所以付 ¥4 买 1A 和 1B（大礼包 1），以及 ¥3 购买 1B ， ¥4 购买 1C 。 \n",
    "不可以购买超出待购清单的物品，尽管购买大礼包 2 更加便宜。</pre>\n",
    "\n",
    "<p> </p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>n == price.length</code></li>\n",
    "\t<li><code>n == needs.length</code></li>\n",
    "\t<li><code>1 <= n <= 6</code></li>\n",
    "\t<li><code>0 <= price[i] <= 10</code></li>\n",
    "\t<li><code>0 <= needs[i] <= 10</code></li>\n",
    "\t<li><code>1 <= special.length <= 100</code></li>\n",
    "\t<li><code>special[i].length == n + 1</code></li>\n",
    "\t<li><code>0 <= special[i][j] <= 50</code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [shopping-offers](https://leetcode.cn/problems/shopping-offers/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [shopping-offers](https://leetcode.cn/problems/shopping-offers/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[2,5]\\n[[3,0,5],[1,2,10]]\\n[3,2]', '[2,3,4]\\n[[1,1,0,4],[2,2,1,9]]\\n[1,2,1]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from functools import lru_cache\n",
    "\n",
    "class Solution:\n",
    "    def shoppingOffers(self, price: List[int], special: List[List[int]], needs: List[int]) -> int:\n",
    "        n = len(price)\n",
    "\n",
    "        # 过滤不需要计算的大礼包，只保留需要计算的大礼包\n",
    "        # filter_special = []\n",
    "        # for sp in special:\n",
    "        #     if sum(sp[i] for i in range(n)) > 0 and sum(sp[i] * price[i] for i in range(n)) > sp[-1]:\n",
    "        #         filter_special.append(sp)\n",
    "\n",
    "        filter_special = special\n",
    "        # 记忆化搜索计算满足购物清单所需花费的最低价格\n",
    "        @lru_cache(None)\n",
    "        def dfs(cur_needs):\n",
    "            # 不购买任何大礼包，原价购买购物清单中的所有物品\n",
    "            min_price = sum(need * price[i] for i, need in enumerate(cur_needs))\n",
    "            for cur_special in filter_special:\n",
    "                special_price = cur_special[-1]\n",
    "                nxt_needs = []\n",
    "                for i in range(n):\n",
    "                    if cur_special[i] > cur_needs[i]:  # 不能购买超出购物清单指定数量的物品\n",
    "                        break\n",
    "                    nxt_needs.append(cur_needs[i] - cur_special[i])\n",
    "                if len(nxt_needs) == n:  # 大礼包可以购买\n",
    "                    min_price = min(min_price, dfs(tuple(nxt_needs)) + special_price)\n",
    "            return min_price\n",
    "\n",
    "        return dfs(tuple(needs))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shoppingOffers(self, price: List[int], special: List[List[int]], needs: List[int]) -> int:\n",
    "        n = len(price)\n",
    "        filter_special = []\n",
    "        for sp in special:\n",
    "            if sum(sp[i] for i in range(n)) > 0 and sum(price[i] * sp[i] for i in range(n)) > sp[-1]:\n",
    "                filter_special.append(sp)\n",
    "        @cache\n",
    "        def dfs(cur_need):\n",
    "            minans = sum(price[i] * cur_need[i] for i in range(n))\n",
    "            for sp in filter_special:\n",
    "                nxt_need = []\n",
    "                for i in range(n):\n",
    "                    if cur_need[i] < sp[i]:\n",
    "                        break\n",
    "                    nxt_need.append(cur_need[i] - sp[i])\n",
    "                if len(nxt_need) == n:\n",
    "                    minans = min(minans, dfs(tuple(nxt_need)) + sp[-1])\n",
    "            return minans\n",
    "\n",
    "        return dfs(tuple(needs))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shoppingOffers(self, price: List[int], special: List[List[int]], needs: List[int]) -> int:\n",
    "        n = len(price)\n",
    "        fliter_special = []\n",
    "        for sp in special:  # 筛选出能够减少成本的特殊礼包\n",
    "            if sum(sp[i] for i in range(n)) > 0 and sum(sp[i] * price[i] for i in range(n)) > sp[-1]:\n",
    "                fliter_special.append(sp)\n",
    "\n",
    "        @cache\n",
    "        def dfs(cur_need):  # 转化为tuple是因为list不可hash化\n",
    "            min_price = sum(price[i] * cur_need[i] for i in range(n))  # 当前所需物品全部单个购买\n",
    "            for cur_special in fliter_special:\n",
    "                special_price = cur_special[-1]  # 当前礼包的价格\n",
    "                next_need = []  # 当前礼包符合的条件数（礼包内的物品不能超过需要值）\n",
    "                for i in range(n):\n",
    "                    if cur_special[i] > cur_need[i]:  # 当礼包内某物品超过需要数\n",
    "                        break\n",
    "                    next_need.append(cur_need[i] - cur_special[i])  # 更新缺少物品信息\n",
    "                if len(next_need) == n:\n",
    "                    min_price = min(min_price, dfs(tuple(next_need)) + special_price)  # 继续搜索\n",
    "\n",
    "            return min_price\n",
    "\n",
    "        return dfs(tuple(needs))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shoppingOffers(self, price: List[int], special: List[List[int]], needs: List[int]) -> int:\n",
    "        n = len(price)\n",
    "        fliter_special = []\n",
    "        for sp in special:  # 筛选出能够减少成本的特殊礼包\n",
    "            if sum(sp[i] for i in range(n)) > 0 and sum(sp[i] * price[i] for i in range(n)) > sp[-1]:\n",
    "                fliter_special.append(sp)\n",
    "\n",
    "        @cache\n",
    "        def dfs(cur_need):\n",
    "            min_price = sum(price[i] * cur_need[i] for i in range(n))  #\n",
    "            for cur_special in fliter_special:\n",
    "                special_price = cur_special[-1]\n",
    "                next_need = []\n",
    "                for i in range(n):\n",
    "                    if cur_special[i] > cur_need[i]:  # 当礼包内某物品超过需要数\n",
    "                        break\n",
    "                    next_need.append(cur_need[i] - cur_special[i])\n",
    "                if len(next_need) == n:\n",
    "                    min_price = min(min_price, dfs(tuple(next_need))+special_price)\n",
    "\n",
    "            return min_price\n",
    "\n",
    "        return dfs(tuple(needs))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shoppingOffers(self, price: List[int], special: List[List[int]], needs: List[int]) -> int:\n",
    "        n = len(price)\n",
    "        filter_special = special\n",
    "        # for sp in special:\n",
    "        #     if sum(sp[i] for i in range(n)) > 0 and sum(price[i] * sp[i] for i in range(n)) > sp[-1]:\n",
    "        #         filter_special.append(sp)\n",
    "        @cache\n",
    "        def dfs(cur_need):\n",
    "            minans = sum(price[i] * cur_need[i] for i in range(n))\n",
    "            for sp in filter_special:\n",
    "                nxt_need = []\n",
    "                for i in range(n):\n",
    "                    if cur_need[i] < sp[i]:\n",
    "                        break\n",
    "                    nxt_need.append(cur_need[i] - sp[i])\n",
    "                if len(nxt_need) == n:\n",
    "                    minans = min(minans, dfs(tuple(nxt_need)) + sp[-1])\n",
    "            return minans\n",
    "\n",
    "        return dfs(tuple(needs))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shoppingOffers(self, price: List[int], special: List[List[int]], needs: List[int]) -> int:\n",
    "        \n",
    "        def search(lefts, cost):\n",
    "            if sum(lefts) == 0:\n",
    "                return cost\n",
    "            res = cost + sum(p*l for p,l in zip(price,lefts))\n",
    "            for i in special:\n",
    "                if all(l >= s for l,s in zip(lefts,i[:-1])):\n",
    "                    new_lefts = [l-s for l,s in zip(lefts,i[:-1])]\n",
    "                    res = min(res,search(new_lefts, cost + i[-1]))\n",
    "            return res\n",
    "\n",
    "        length = len(special)\n",
    "        rem = []\n",
    "        for i in range(length):\n",
    "            if sum(p*s for p,s in zip(price,special[i][:-1])) <= special[i][-1]:\n",
    "                rem.append(i)\n",
    "        rem.reverse()\n",
    "        for i in rem:\n",
    "            special.pop(i)\n",
    "        print(special)\n",
    "        return search(needs, 0)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shoppingOffers(self, price: List[int], special: List[List[int]], needs: List[int]) -> int:\n",
    "        @cache\n",
    "        def dfs(cnts):\n",
    "            if all(c == 0 for c in cnts):\n",
    "                return 0\n",
    "            res = sum(x * y for x,y in zip(cnts, price))\n",
    "            for *c, p in special:\n",
    "                cur = tuple(y - x for x, y in zip(c, cnts))\n",
    "                if all(v >=0 for v in cur):\n",
    "                    res = min(res, dfs(cur)+p)\n",
    "            return res\n",
    "        return dfs(tuple(needs))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def dfs(self, step, price, special, needs, tab):\n",
    "        x = tuple(needs)\n",
    "        if x in tab[step]:\n",
    "            return tab[step][x]\n",
    "        # 没有大礼包的情况，初始化f[0][j...]：\n",
    "        if step==0:\n",
    "            s = 0\n",
    "            for i in range(0, len(price)):\n",
    "                s+= needs[i]*price[i]\n",
    "            tab[step][x] = s\n",
    "            return s\n",
    "        # 第step个大礼包不选：  f[i-1][j...]\n",
    "        tab[step][x] = self.dfs(step-1, price, special, needs, tab)\n",
    "        # 第step个大礼包选一个: f[i][j-x1...]\n",
    "        newNeeds = []\n",
    "        for i in range(len(needs)):\n",
    "            if needs[i] < special[step-1][i]:\n",
    "                return tab[step][x]\n",
    "            newNeeds.append(needs[i] - special[step-1][i])\n",
    "        f = special[step-1][-1] + self.dfs(step, price, special, newNeeds, tab)\n",
    "\n",
    "        tab[step][x] = min(tab[step][x], f)\n",
    "        return tab[step][x]\n",
    "                \n",
    "    def shoppingOffers(self, price: List[int], special: List[List[int]], needs: List[int]) -> int:\n",
    "        tab = [{} for _ in range(len(special)+1)]\n",
    "        return self.dfs(len(special), price, special, needs, tab)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import Dict, List\n",
    "\n",
    "def tos(idx:int, need:List[int]) -> str:\n",
    "    s = '_'.join(map(str, need))\n",
    "    return f'{idx}-{s}'\n",
    "\n",
    "class Solution:\n",
    "    price:List[int]\n",
    "    special:List[List[int]]\n",
    "    cache:Dict[str, int]\n",
    "\n",
    "    def dfs(self, idx:int, need:List[int], p:int) -> int:\n",
    "        s = tos(idx, need)\n",
    "        if s in self.cache:\n",
    "            return p + self.cache[s]\n",
    "        spLength = len(self.special)\n",
    "        if idx == spLength:\n",
    "            res = 0\n",
    "            for i, v in enumerate(need):\n",
    "                res += v * self.price[i]\n",
    "            self.cache[s] = res\n",
    "            return res + p\n",
    "        sp = self.special[idx]\n",
    "        pLength = len(self.price)\n",
    "        res = self.dfs(idx + 1, need, p)\n",
    "        currNum = 1\n",
    "        while True:\n",
    "            good = True\n",
    "            for i in range(pLength):\n",
    "                need[i] -= currNum * sp[i]\n",
    "            if min(need) < 0:\n",
    "                good = False\n",
    "            if good:\n",
    "                res = min(res, self.dfs(idx + 1, need, p + currNum * sp[-1]))\n",
    "            for i in range(pLength):\n",
    "                need[i] += currNum * sp[i]\n",
    "            currNum += 1\n",
    "            if not good:\n",
    "                break\n",
    "        self.cache[s] = res - p\n",
    "        return res\n",
    "\n",
    "    def shoppingOffers(self, price: List[int], special: List[List[int]], needs: List[int]) -> int:\n",
    "        self.price = price\n",
    "        self.special = special\n",
    "        self.cache = {}\n",
    "        return self.dfs(0, needs, 0)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shoppingOffers(self, price: List[int], special: List[List[int]], needs: List[int]) -> int:\n",
    "        n = len(price)\n",
    "        sp_table = [[] for _ in range(n)]\n",
    "        for sp_idx, sp in enumerate(special):\n",
    "            for item_idx in range(n):\n",
    "                if sp[item_idx] > 0:\n",
    "                    sp_table[item_idx].append(sp_idx)\n",
    "\n",
    "        @cache\n",
    "        def dfs(needs):\n",
    "            nonlocal sp_table, n\n",
    "\n",
    "            nxt_item = -1\n",
    "            for i in range(n):\n",
    "                if needs[i] > 0:\n",
    "                    nxt_item = i\n",
    "                    break\n",
    "            \n",
    "            if nxt_item == -1:\n",
    "                return 0\n",
    "\n",
    "            needs = list(needs)\n",
    "            # do not use special\n",
    "            needs[nxt_item] -= 1\n",
    "            min_price = dfs(tuple(needs)) + price[nxt_item]\n",
    "            needs[nxt_item] += 1\n",
    "\n",
    "            # use special\n",
    "            for sp_idx in sp_table[nxt_item]:\n",
    "                useful = True\n",
    "                for item_idx in range(n):\n",
    "                    if special[sp_idx][item_idx] > needs[item_idx]:\n",
    "                        useful = False\n",
    "                        break\n",
    "                if useful:\n",
    "                    for item_idx in range(n):\n",
    "                        needs[item_idx] -= special[sp_idx][item_idx]\n",
    "                    min_price = min(min_price, dfs(tuple(needs)) + special[sp_idx][-1])\n",
    "                    for item_idx in range(n):\n",
    "                        needs[item_idx] += special[sp_idx][item_idx]\n",
    "            return min_price\n",
    "\n",
    "        return dfs(tuple(needs))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shoppingOffers(self, price: List[int], special: List[List[int]], needs: List[int]) -> int:\n",
    "        n = len(price)\n",
    "\n",
    "        sp_indices = []\n",
    "        for i in range(len(special)):\n",
    "            if sum(special[i][j] * price[j] for j in range(n)) > special[i][-1]:\n",
    "                sp_indices.append(i)\n",
    "\n",
    "        sp_table = [[] for _ in range(n)]\n",
    "        for sp_idx in sp_indices:\n",
    "            for item_idx in range(n):\n",
    "                if special[sp_idx][item_idx] > 0:\n",
    "                    sp_table[item_idx].append(sp_idx)\n",
    "\n",
    "        @cache\n",
    "        def dfs(needs):\n",
    "            nonlocal sp_table, n\n",
    "\n",
    "            nxt_item = -1\n",
    "            for i in range(n):\n",
    "                if needs[i] > 0:\n",
    "                    nxt_item = i\n",
    "                    break\n",
    "            \n",
    "            if nxt_item == -1:\n",
    "                return 0\n",
    "\n",
    "            needs = list(needs)\n",
    "            # do not use special\n",
    "            needs[nxt_item] -= 1\n",
    "            min_price = dfs(tuple(needs)) + price[nxt_item]\n",
    "            needs[nxt_item] += 1\n",
    "\n",
    "            # use special\n",
    "            for sp_idx in sp_table[nxt_item]:\n",
    "                useful = True\n",
    "                for item_idx in range(n):\n",
    "                    if special[sp_idx][item_idx] > needs[item_idx]:\n",
    "                        useful = False\n",
    "                        break\n",
    "                if useful:\n",
    "                    for item_idx in range(n):\n",
    "                        needs[item_idx] -= special[sp_idx][item_idx]\n",
    "                    min_price = min(min_price, dfs(tuple(needs)) + special[sp_idx][-1])\n",
    "                    for item_idx in range(n):\n",
    "                        needs[item_idx] += special[sp_idx][item_idx]\n",
    "            return min_price\n",
    "\n",
    "        return dfs(tuple(needs))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shoppingOffers(self, price: List[int], special: List[List[int]], needs: List[int]) -> int:\n",
    "        n = len(price)\n",
    "\n",
    "        sp_indices = []\n",
    "        for i in range(len(special)):\n",
    "            if sum(special[i][j] * price[j] for j in range(n)) > special[i][-1]:\n",
    "                sp_indices.append(i)\n",
    "\n",
    "        sp_table = [[] for _ in range(n)]\n",
    "        for sp_idx in sp_indices:\n",
    "            for item_idx in range(n):\n",
    "                if special[sp_idx][item_idx] > 0:\n",
    "                    sp_table[item_idx].append(sp_idx)\n",
    "\n",
    "        @cache\n",
    "        def dfs(needs):\n",
    "            nonlocal sp_table, n\n",
    "\n",
    "            nxt_item = -1\n",
    "            for i in range(n):\n",
    "                if needs[i] > 0:\n",
    "                    nxt_item = i\n",
    "                    break\n",
    "            \n",
    "            if nxt_item == -1:\n",
    "                return 0\n",
    "\n",
    "            needs = list(needs)\n",
    "            # do not use special\n",
    "            needs[nxt_item] -= 1\n",
    "            min_price = dfs(tuple(needs)) + price[nxt_item]\n",
    "            needs[nxt_item] += 1\n",
    "\n",
    "            # use special\n",
    "            for sp_idx in sp_table[nxt_item]:\n",
    "                useful = True\n",
    "                for item_idx in range(n):\n",
    "                    if special[sp_idx][item_idx] > needs[item_idx]:\n",
    "                        useful = False\n",
    "                        break\n",
    "                if useful:\n",
    "                    for item_idx in range(n):\n",
    "                        needs[item_idx] -= special[sp_idx][item_idx]\n",
    "                    min_price = min(min_price, dfs(tuple(needs)) + special[sp_idx][-1])\n",
    "                    for item_idx in range(n):\n",
    "                        needs[item_idx] += special[sp_idx][item_idx]\n",
    "            return min_price\n",
    "\n",
    "        return dfs(tuple(needs))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shoppingOffers(self, price: List[int], special: List[List[int]], needs: List[int]) -> int:\n",
    "        n = len(price)\n",
    "        ans = float(\"inf\")\n",
    "\n",
    "        for i, v in enumerate(price):\n",
    "            tmp = [0] * n\n",
    "            tmp[i] = 1\n",
    "            special.append(tmp + [v])\n",
    "        \n",
    "        cur = needs[:]\n",
    "        @cache\n",
    "        def dfs(cost: int, need) -> None:\n",
    "            nonlocal ans\n",
    "            if cost >= ans:\n",
    "                return\n",
    "            if need < 0:\n",
    "                return\n",
    "            elif need == 0:\n",
    "                ans = min(ans, cost)\n",
    "                return\n",
    "\n",
    "            for giftBag in special:\n",
    "                cnt = {i:numbers for i, numbers in enumerate(giftBag[:-1:])}\n",
    "                if all(cur[x]>=cnt[x] for x in cnt):\n",
    "                    # +\n",
    "                    for x in cnt:\n",
    "                        cur[x] -= cnt[x]\n",
    "                        need -= cnt[x]\n",
    "                    cost += giftBag[-1]\n",
    "                    dfs(cost, need)\n",
    "                    cost -= giftBag[-1]\n",
    "                    for x in cnt:\n",
    "                        cur[x] += cnt[x]\n",
    "                        need += cnt[x]\n",
    "        dfs(0, sum(needs))\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shoppingOffers(self, price: List[int], special: List[List[int]], needs: List[int]) -> int:\n",
    "        @cache\n",
    "        def dfs(j, bNeeds):\n",
    "            if j == m:\n",
    "                return sum(price[i] * ((bNeeds >> ((n-i-1)*4)) & 15) for i in range(n))\n",
    "            else:\n",
    "                ans = dfs(j+1, bNeeds)\n",
    "                sp = 0\n",
    "                while bNeeds:\n",
    "                    for i in range(n):\n",
    "                        c = ((bNeeds >> ((n-i-1)*4)) & 15)\n",
    "                        if c >= special[j][i]:\n",
    "                            bNeeds -= (special[j][i] << ((n-i-1)*4))\n",
    "                        else:\n",
    "                            print(j, bNeeds, ans)\n",
    "                            return ans\n",
    "                    sp += special[j][-1]\n",
    "                    ans = min(ans, sp + dfs(j+1, bNeeds)) # O(100*6)), O(100*6)\n",
    "                return ans\n",
    "\n",
    "        n = len(price)\n",
    "        m = len(special)\n",
    "        bNeeds = 0\n",
    "        for need in needs:\n",
    "            bNeeds <<= 4\n",
    "            bNeeds += need\n",
    "        return dfs(0, bNeeds)\n",
    "\n",
    "        '''\n",
    "        @cache\n",
    "        def dfs(bNeeds):\n",
    "            ans = 0\n",
    "            for i in range(n):\n",
    "                ans += price[i] * ((bNeeds >> ((n-i-1)*4)) & 15)\n",
    "            for s in special:\n",
    "                nNeeds = bNeeds\n",
    "                for i in range(n):\n",
    "                    c = ((nNeeds >> ((n-i-1)*4)) & 15)\n",
    "                    if c >= s[i]:\n",
    "                        nNeeds -= (s[i] << ((n-i-1)*4))\n",
    "                    else:\n",
    "                        nNeeds = -1\n",
    "                        break\n",
    "                if nNeeds >= 0:\n",
    "                    ans = min(ans, s[-1] + dfs(nNeeds)) # O(100*6)), O(100*6)\n",
    "            return ans\n",
    "\n",
    "        n = len(price)\n",
    "        bNeeds = 0\n",
    "        for need in needs:\n",
    "            bNeeds <<= 4\n",
    "            bNeeds += need\n",
    "        return dfs(bNeeds)\n",
    "        '''\n",
    "\n",
    "        '''\n",
    "        def dfs(tNeeds):\n",
    "            ans = sum(price[i] * c for i, c in enumerate(tNeeds))\n",
    "            for s in special:\n",
    "                nNeeds = []\n",
    "                for i in range(n):\n",
    "                    if tNeeds[i] >= s[i]:\n",
    "                        nNeeds.append(tNeeds[i] - s[i])\n",
    "                    else:\n",
    "                        break\n",
    "                if len(nNeeds) == n:\n",
    "                    ans = min(ans, s[-1] + dfs(nNeeds)) # O(100**(6*c)), O(6*c)\n",
    "            return ans\n",
    "\n",
    "        n = len(price)\n",
    "        return dfs(needs)\n",
    "        '''\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shoppingOffers(self, price: List[int], special: List[List[int]], needs: List[int]) -> int:\n",
    "        sp = []\n",
    "        for s in special:\n",
    "            if sum(s[i] for i in range(len(price))) > 0 and sum(s[i] * price[i] for i in range(len(price))) > s[-1]:\n",
    "                sp.append(s)\n",
    "        nd = [1]\n",
    "        for n in needs:\n",
    "            nd.append(nd[-1] * (n + 1))\n",
    "        total = nd[-1]\n",
    "        dp = [0xffffff] * total\n",
    "        self.total = 0\n",
    "        def n2l2p(i):\n",
    "            res = 0\n",
    "            for j in range(len(price)):\n",
    "                res += price[j] * (i % nd[j + 1] // nd[j])\n",
    "            return res\n",
    "\n",
    "        def dfs(i):\n",
    "            if i == 0:\n",
    "                dp[i] = 0\n",
    "            if dp[i] < 0xffffff:\n",
    "                return dp[i]\n",
    "            self.total += 1\n",
    "            for t in sp:\n",
    "                j_ = 0\n",
    "                for j in range(len(price)):\n",
    "                    if i % nd[j + 1] // nd[j] < t[j]:\n",
    "                        break\n",
    "                    j_ += nd[j] * t[j]\n",
    "                else:\n",
    "                    dp[i] = min(dp[i], t[-1] + dfs(i - j_))\n",
    "            dp[i] = min(dp[i], n2l2p(i))\n",
    "            return dp[i]\n",
    "\n",
    "        dfs(total - 1)\n",
    "        return dp[-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "\n",
    "    def dfs(self, needs, special_start):\n",
    "        if max(needs) == 0:\n",
    "            return 0\n",
    "        \n",
    "        key = tuple(needs+[special_start])\n",
    "        if key in self.states.keys():\n",
    "            return self.states[key]\n",
    "        \n",
    "        res = sum([needs[i]*self.price[i] for i in range(len(needs))])\n",
    "\n",
    "        if special_start >= len(self.special):\n",
    "            return res\n",
    "        \n",
    "        if max(self.special[special_start][:-1]) <= 0:\n",
    "            return self.dfs(needs, special_start+1)\n",
    "\n",
    "        num = 0\n",
    "        while True:\n",
    "            taken = [num*self.special[special_start][i] for i in range(len(needs))]\n",
    "            remains = [needs[i]-taken[i] for i in range(len(needs))]\n",
    "            cost = self.special[special_start][-1] * num\n",
    "\n",
    "            if min(remains) < 0:\n",
    "                break\n",
    "            \n",
    "            if cost > res:\n",
    "                break\n",
    "            \n",
    "            res = min(res, cost + self.dfs(remains, special_start+1))\n",
    "\n",
    "            num += 1\n",
    "\n",
    "        self.states[key] = res        \n",
    "        return res\n",
    "\n",
    "    def shoppingOffers(self, price: List[int], special: List[List[int]], needs: List[int]) -> int:\n",
    "\n",
    "        self.price = price\n",
    "        self.special = special\n",
    "        self.states = {}\n",
    "\n",
    "        return self.dfs(needs, 0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from functools import lru_cache\r\n",
    "\r\n",
    "class Solution:\r\n",
    "    def shoppingOffers(self, price: [int], special: [[int]], needs: [int]) -> int:\r\n",
    "        n = len(price)\r\n",
    "        sp_n = len(special)\r\n",
    "\r\n",
    "        ans = float('inf')\r\n",
    "        @lru_cache(None)\r\n",
    "        def dfs(need: tuple, k: int) -> int:\r\n",
    "            if k==0:\r\n",
    "                tp = 0\r\n",
    "                for i in range(n):\r\n",
    "                    tp += need[i]*price[i]\r\n",
    "                return tp\r\n",
    "\r\n",
    "            k -= 1\r\n",
    "            # use k / not\r\n",
    "            tp = dfs(need, k)\r\n",
    "\r\n",
    "            new_need = [need[i]-special[k][i] for i in range(n)]\r\n",
    "            cnt = 1\r\n",
    "            while min(new_need) >= 0:\r\n",
    "                tp = min(tp, dfs(tuple(new_need), k)+special[k][-1]*cnt)\r\n",
    "                new_need = [new_need[i]-special[k][i] for i in range(n)]\r\n",
    "                cnt += 1\r\n",
    "            return tp\r\n",
    "        return dfs(tuple(needs), sp_n)\r\n",
    "                    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shoppingOffers(self, price: List[int], special: List[List[int]], needs: List[int]) -> int:\n",
    "        # 过滤一些不如单买便宜和其中超出购买物品数量的礼包\n",
    "        special = list(filter(lambda s: s[-1] < sum(n * price[i] for i, n in enumerate(s[:-1])) and all(a <= b for a, b in zip(s, needs)), special))\n",
    "\n",
    "        @cache\n",
    "        def dfs(idx, needs):\n",
    "            if idx == len(special):\n",
    "                return sum(p * n for p, n in zip(price, needs))\n",
    "            spe = special[idx]\n",
    "            ans = dfs(idx + 1, tuple(needs))\n",
    "            cnt = 1\n",
    "            # 枚举当前礼包购买的数量\n",
    "            while 1:\n",
    "                lis = []\n",
    "                for n, s in zip(needs, spe[:-1]):\n",
    "                    # 若购买cnt个超出\n",
    "                    if s * cnt > n: return ans\n",
    "                    lis.append(n - s * cnt)\n",
    "                ans = min(ans, spe[-1] * cnt + dfs(idx + 1, tuple(lis)))\n",
    "                cnt += 1\n",
    "            return ans\n",
    "        \n",
    "        return dfs(0, tuple(needs))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from functools import lru_cache\n",
    "class Solution:\n",
    "    def shoppingOffers(self, price: List[int], special: List[List[int]], needs: List[int]) -> int:\n",
    "        m = len(price)\n",
    "\n",
    "        @cache\n",
    "        def help(i, need):\n",
    "            #ans = 0\n",
    "            flag = True\n",
    "            new = list(need)\n",
    "            if sum(need) == 0:\n",
    "                return 0\n",
    "\n",
    "            if i == len(special):\n",
    "                return sys.maxsize\n",
    "\n",
    "            #不用大礼包\n",
    "            ans = 0\n",
    "            for nd, p in zip(need, price):\n",
    "                ans += nd * p    \n",
    "            #判断是否用不成第i个礼包\n",
    "            for k in range(m):\n",
    "                if special[i][k] > need[k]:\n",
    "                    flag = False\n",
    "                    break\n",
    "                new[k] -= special[i][k]\n",
    "            #用不成第i个礼包\n",
    "            ans = min(ans, help(i+1, need))\n",
    "            if not flag:\n",
    "                return ans\n",
    "            #用得成第i个礼包\n",
    "            return min(ans, help(i, tuple(new)) + special[i][-1])\n",
    "\n",
    "        return help(0, tuple(needs))\n",
    "\n",
    "\n",
    "\n",
    "                \n",
    "\n",
    "\n",
    "        \n",
    "\n",
    "            \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shoppingOffers(self, price: List[int], special: List[List[int]], needs: List[int]) -> int:\n",
    "        @lru_cache(None)\n",
    "        def dfs(i, needs):\n",
    "            if i==-1:\n",
    "                return sum(a*b for a,b in zip(price, needs))\n",
    "            res = dfs(i-1, needs)\n",
    "            A = tuple(b-a for a,b in zip(special[i], needs))\n",
    "            if all(a>=0 for a in A):\n",
    "                res = min(res, dfs(i, A)+special[i][-1])\n",
    "            return res\n",
    "\n",
    "        return dfs(len(special)-1, tuple(needs))\n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shoppingOffers(self, price: List[int], special: List[List[int]], needs: List[int]) -> int:\n",
    "        n = len(price)\n",
    "        res = sum(price[i] * needs[i] for i in range(n))\n",
    "        need = ' '.join([str(i) for i in needs])\n",
    "\n",
    "        @cache\n",
    "        def search(need, s):\n",
    "            cur = [int(i) for i in need.split()]\n",
    "            if not any(cur):\n",
    "                nonlocal res\n",
    "                res = min(s, res)\n",
    "            \n",
    "            for r in special:\n",
    "                p = r[-1]\n",
    "                for idx, item in enumerate(r[:-1]):\n",
    "                    if item > cur[idx]:\n",
    "                        break\n",
    "                else:\n",
    "                    for idx, item in enumerate(r[:-1]):\n",
    "                        cur[idx] -= item\n",
    "                    search(' '.join([str(i) for i in cur]), s+p)\n",
    "                    for idx, item in enumerate(r[:-1]):\n",
    "                        cur[idx] += item\n",
    "            for idx, p in enumerate(price):\n",
    "                if cur[idx]:\n",
    "                    tmp = cur[idx]\n",
    "                    cur[idx] = 0\n",
    "                    search(' '.join([str(i) for i in cur]), s+p*tmp)\n",
    "                    cur[idx] = tmp\n",
    "\n",
    "\n",
    "        search(need, 0)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "\n",
    "    # 记忆化搜索\n",
    "    def shoppingOffers(self, price: List[int], special: List[List[int]], needs: List[int]) -> int:\n",
    "        def memo(func):\n",
    "            cache = {}\n",
    "\n",
    "            def wrapper(*args):\n",
    "                key = (tuple(args[0]), args[1])\n",
    "                if key not in cache:\n",
    "                    cache[key] = func(*args)\n",
    "                return cache[key]\n",
    "\n",
    "            return wrapper\n",
    "\n",
    "        @memo\n",
    "        def recur(order, cost):\n",
    "            nonlocal ans\n",
    "            if order == end:\n",
    "                ans = min(ans, cost)\n",
    "                return\n",
    "            # 购买大礼包\n",
    "            for item in special:\n",
    "                tmp, can_buy = order[:], True\n",
    "                for i in range(n):\n",
    "                    tmp[i] -= item[i]\n",
    "                    if tmp[i] < 0:\n",
    "                        can_buy = False\n",
    "                        break\n",
    "                if not can_buy:\n",
    "                    continue\n",
    "                recur(tmp, cost + item[-1])\n",
    "            # 购买单品\n",
    "            for i, v in enumerate(price):\n",
    "                if order[i] == 0:\n",
    "                    continue\n",
    "                num, order[i] = order[i], 0\n",
    "                recur(order, cost + price[i] * num)\n",
    "                order[i] = num            \n",
    "\n",
    "        ans, n = float('inf'), len(needs)\n",
    "        end = [0] * n\n",
    "        recur(needs, 0)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shoppingOffers(self, price: List[int], special: List[List[int]], needs: List[int]) -> int:\n",
    "        ns = [s for s in special if sum(price[_]*s[_] for _ in range(len(price)))>s[-1]]\n",
    "        special = ns\n",
    "\n",
    "        M = len(price)\n",
    "        N = len(special)\n",
    "\n",
    "        mem = {}\n",
    "\n",
    "        def h(a):\n",
    "            return ','.join(str(_) for _ in a)\n",
    "\n",
    "        def f(arr):\n",
    "            if any(_<0 for _ in arr): return float('inf')\n",
    "            if sum(arr)==0: return 0\n",
    "            k = h(arr)\n",
    "            if k in mem: return mem[k]\n",
    "            ret = float('inf')\n",
    "            \n",
    "            for i in range(N):\n",
    "                s = special[i]\n",
    "                for j in range(M):\n",
    "                    arr[j] -= s[j]\n",
    "                v = f(arr) + s[-1]\n",
    "                ret = min(v, ret)\n",
    "                for j in range(M):\n",
    "                    arr[j] += s[j]\n",
    "\n",
    "            if ret==float('inf'):\n",
    "                for i in range(M):\n",
    "                    arr[i] -= 1\n",
    "                    v = f(arr) + price[i]\n",
    "                    ret = min(v, ret)\n",
    "                    arr[i] += 1\n",
    "\n",
    "            mem[k] = ret\n",
    "            return ret\n",
    "\n",
    "        return f(needs)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shoppingOffers(self, price: List[int], special: List[List[int]], needs: List[int]) -> int:\n",
    "        n = len(price)\n",
    "        ans = float('inf')\n",
    "        final = tuple(needs)\n",
    "\n",
    "        @cache\n",
    "        def dfs(cur, p):\n",
    "            nonlocal ans, final\n",
    "            if cur == final:\n",
    "                ans = min(ans, p)\n",
    "                return\n",
    "            for s in special:\n",
    "                update = list(cur)\n",
    "                i = 0\n",
    "                while i < n and s[i] + cur[i] <= needs[i]:\n",
    "                    update[i] += s[i]\n",
    "                    i += 1\n",
    "                if i == n:\n",
    "                    dfs(tuple(update), p + s[n])\n",
    "\n",
    "            for i in range(n):\n",
    "                update = list(cur)\n",
    "                if cur[i] < needs[i]:\n",
    "                    update[i] = needs[i]\n",
    "                    dfs(tuple(update), p + (needs[i] - cur[i]) * price[i])\n",
    "\n",
    "            return\n",
    "        \n",
    "        dfs(tuple([0] * n), 0)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shoppingOffers(self, price: List[int], special: List[List[int]], needs: List[int]) -> int:\n",
    "        memo = {}\n",
    "        \n",
    "        def helper(sl, nee):\n",
    "            if (sl, nee) in memo:\n",
    "                return memo[(sl, nee)]\n",
    "            if sl==0:\n",
    "                cur = 0\n",
    "                for i in range(len(price)):\n",
    "                    cur += (price[i] * nee[i])\n",
    "                memo[(sl, nee)] = cur\n",
    "                return cur\n",
    "            ans = float('inf')\n",
    "            for i in range(7):\n",
    "                newnee = []\n",
    "                for j in range(len(price)):\n",
    "                    newnee.append(nee[j] - special[sl-1][j] * i)\n",
    "                hasneg = False\n",
    "                for el in newnee:\n",
    "                    if el < 0:\n",
    "                        hasneg = True\n",
    "                if hasneg:\n",
    "                    break\n",
    "                ans = min(ans, i*special[sl-1][-1] +helper(sl-1, tuple(newnee)))\n",
    "            memo[(sl, nee)] = ans\n",
    "            return ans\n",
    "        return helper(len(special), tuple(needs))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shoppingOffers(self, price: List[int], special: List[List[int]], needs: List[int]) -> int:\n",
    "        n = len(price)\n",
    "        res = sum(price[i] * needs[i] for i in range(n))\n",
    "        need = tuple(needs)\n",
    "\n",
    "        @cache\n",
    "        def search(need, s):\n",
    "            if not any(need):\n",
    "                nonlocal res\n",
    "                res = min(s, res)\n",
    "            cur = list(need)\n",
    "            for r in special:\n",
    "                p = r[-1]\n",
    "                for idx, item in enumerate(r[:-1]):\n",
    "                    if item > cur[idx]:\n",
    "                        break\n",
    "                else:\n",
    "                    for idx, item in enumerate(r[:-1]):\n",
    "                        cur[idx] -= item\n",
    "                    search(tuple(cur), s+p)\n",
    "                    for idx, item in enumerate(r[:-1]):\n",
    "                        cur[idx] += item\n",
    "            for idx, p in enumerate(price):\n",
    "                if cur[idx]:\n",
    "                    tmp = cur[idx]\n",
    "                    cur[idx] = 0\n",
    "                    search(tuple(cur), s+p*tmp)\n",
    "                    cur[idx] = tmp\n",
    "\n",
    "\n",
    "        search(need, 0)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "\tdef shoppingOffers(self, price, special, needs):\n",
    "\t\tn = len(price)\n",
    "\t\tc = {tuple([0] * n): 0}\n",
    "\t\ts = list(special)\n",
    "\t\tfor i in range(n):\n",
    "\t\t\ts.append([1 if i == j else 0 for j in range(n)] + [price[i]])\n",
    "\t\tfor x in s:\n",
    "\t\t\td = {**c}\n",
    "\t\t\tfor k, v in c.items():\n",
    "\t\t\t\tfor i in range(1, 11):\n",
    "\t\t\t\t\tt, w = [k[j] + x[j] * i for j in range(n)], v + x[-1] * i\n",
    "\t\t\t\t\tif d.get(tuple(needs), math.inf) < w: break\n",
    "\t\t\t\t\tif any(t[j] > needs[j] for j in range(n)): break\n",
    "\t\t\t\t\td[tuple(t)] = min(d.get(tuple(t), math.inf), w)\n",
    "\t\t\tc = d\n",
    "\t\treturn c.get(tuple(needs), math.inf)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shoppingOffers(self, price: List[int], special: List[List[int]], needs: List[int]) -> int:\n",
    "        candi = []\n",
    "        n = len(price)\n",
    "        for s in special:\n",
    "            if all(s[i] <= needs[i] for i in range(n)):\n",
    "                tmp = 0\n",
    "                for j in range(n):\n",
    "                    tmp += s[j] * price[j]\n",
    "                if tmp > s[-1]:\n",
    "                    candi.append(s)\n",
    "        m = len(candi)\n",
    "        if not candi:\n",
    "            return sum(price[i] * needs[i] for i in range(n))\n",
    "\n",
    "        @cache\n",
    "        def dfs(i, tup):\n",
    "            if i == m:\n",
    "                res = 0\n",
    "                for j in range(n):\n",
    "                    res += price[j] * tup[j]\n",
    "                return res \n",
    "            if i == m - 1:\n",
    "                mx = min(tup[j] // candi[i][j] if candi[i][j] else inf for j in range(n))\n",
    "                tmp = [0] * n \n",
    "                for j in range(n):\n",
    "                    tmp[j] = tup[j] - mx * candi[i][j]\n",
    "                return dfs(i + 1, tuple(tmp)) + mx * candi[i][-1]\n",
    "            mx = min(tup[j] // candi[i][j] if candi[i][j] else inf for j in range(n))\n",
    "            res = dfs(i + 1, tup)\n",
    "            for k in range(1, mx + 1):\n",
    "                tmp = [0] * n \n",
    "                for j in range(n):\n",
    "                    tmp[j] = tup[j] - k * candi[i][j]\n",
    "                res = min(res, dfs(i + 1, tuple(tmp)) + k * candi[i][-1])    \n",
    "            return res \n",
    "        \n",
    "        return dfs(0, tuple(needs))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shoppingOffers(self, price: List[int], special: List[List[int]], needs: List[int]) -> int:\n",
    "        n = len(price)\n",
    "        res = sum(price[i] * needs[i] for i in range(n))\n",
    "        need = tuple(needs)\n",
    "\n",
    "        @lru_cache(None)\n",
    "        def search(need, s):\n",
    "            if not any(need):\n",
    "                nonlocal res\n",
    "                res = min(s, res)\n",
    "            for r in special:\n",
    "                p = r[-1]\n",
    "                nxt = []\n",
    "                for idx, item in enumerate(r[:-1]):\n",
    "                    if item > need[idx]:\n",
    "                        break\n",
    "                    nxt.append(need[idx] - item)\n",
    "                else:\n",
    "                    search(tuple(nxt), s+p)\n",
    "                    \n",
    "            for idx, p in enumerate(price):\n",
    "                if need[idx]:\n",
    "                    search(tuple(need[i] if i != idx else 0 for i in range(n)), s+p*need[idx])\n",
    "\n",
    "\n",
    "        search(need, 0)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import math\n",
    "class Solution:\n",
    "    def shoppingOffers(self, price, special, needs) -> int:\n",
    "        def checkall(needs):\n",
    "            for i in needs:\n",
    "                if i != 0:\n",
    "                    return False\n",
    "            return True\n",
    "\n",
    "        def canuse(needs, special):\n",
    "            mini = math.inf\n",
    "            for i in range(len(needs)):\n",
    "                if special[i] != 0:\n",
    "                    mini = min(mini, needs[i] // special[i])\n",
    "            if mini == math.inf:\n",
    "                return 0\n",
    "            else:\n",
    "                return mini\n",
    "\n",
    "        def shoppingOffers_help(price, special, needs, special_ind):\n",
    "            hashval = (str(needs), special_ind)\n",
    "            if hashval in hashmap:\n",
    "                return hashmap[hashval]\n",
    "            if checkall(needs):\n",
    "                return 0\n",
    "            if special_ind == len(special):\n",
    "                tot = sum([price[i] * needs[i] for i in range(len(needs))])\n",
    "                return tot\n",
    "            \n",
    "            p = math.inf\n",
    "            if special_ind < len(special):\n",
    "                for num in range(canuse(needs, special[special_ind]) + 1):\n",
    "                    for i in range(len(needs)):\n",
    "                        needs[i] -= special[special_ind][i] * num\n",
    "                    p = min(p, shoppingOffers_help(price, special, needs, special_ind + 1) + num * special[special_ind][-1])\n",
    "                    for i in range(len(needs)):\n",
    "                        needs[i] += special[special_ind][i] * num\n",
    "            hashmap[hashval] = p\n",
    "            return p\n",
    "        \n",
    "        hashmap = dict()\n",
    "        return shoppingOffers_help(price, special, needs, 0)\n",
    "                    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import math\n",
    "class Solution:\n",
    "    def shoppingOffers(self, price, special, needs) -> int:\n",
    "        def checkall(needs):\n",
    "            for i in needs:\n",
    "                if i != 0:\n",
    "                    return False\n",
    "            return True\n",
    "\n",
    "        def canuse(needs, special):\n",
    "            mini = math.inf\n",
    "            for i in range(len(needs)):\n",
    "                if special[i] != 0:\n",
    "                    mini = min(mini, needs[i] // special[i])\n",
    "            if mini == math.inf:\n",
    "                return 0\n",
    "            else:\n",
    "                return mini\n",
    "\n",
    "        def shoppingOffers_help(price, special, needs, special_ind):\n",
    "            hashval = (str(needs), special_ind)\n",
    "            if hashval in hashmap:\n",
    "                return hashmap[hashval]\n",
    "            if checkall(needs):\n",
    "                hashmap[hashval] = 0\n",
    "                return 0\n",
    "            if special_ind == len(special):\n",
    "                tot = sum([price[i] * needs[i] for i in range(len(needs))])\n",
    "                hashmap[hashval] = tot\n",
    "                return tot\n",
    "            \n",
    "            p = math.inf\n",
    "            if special_ind < len(special):\n",
    "                for num in range(canuse(needs, special[special_ind]) + 1):\n",
    "                    for i in range(len(needs)):\n",
    "                        needs[i] -= special[special_ind][i] * num\n",
    "                    p = min(p, shoppingOffers_help(price, special, needs, special_ind + 1) + num * special[special_ind][-1])\n",
    "                    for i in range(len(needs)):\n",
    "                        needs[i] += special[special_ind][i] * num\n",
    "            hashmap[hashval] = p\n",
    "            return p\n",
    "        \n",
    "        hashmap = dict()\n",
    "        return shoppingOffers_help(price, special, needs, 0)\n",
    "                    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import copy\n",
    "class Solution:\n",
    "    def shoppingOffers(self, price: List[int], special: List[List[int]], needs: List[int]) -> int:\n",
    "        n = len(price)\n",
    "        price = price + [0] * (6 - n)\n",
    "        needs = needs + [0] * (6 - n)\n",
    "        for i in range(len(special)):\n",
    "            special[i] = special[i][:n] + [0] * (6 - n) + [special[i][-1]]\n",
    "        #print(price, needs, special)\n",
    "        dp = 0\n",
    "        for need in reversed(needs):\n",
    "            newdp = []\n",
    "            for i in range(need + 1):\n",
    "               newdp.append(copy.deepcopy(dp))\n",
    "            dp = newdp\n",
    "        for a in range(needs[0] + 1):\n",
    "            for b in range(needs[1] + 1):\n",
    "                for c in range(needs[2] + 1):\n",
    "                    for d in range(needs[3] + 1):\n",
    "                        for e in range(needs[4] + 1):\n",
    "                            for f in range(needs[5] + 1):\n",
    "                                dp[a][b][c][d][e][f] = a * price[0] + b * price[1] + c * price[2] + d * price[3] + e * price[4] + f * price[5]\n",
    "        print(dp)\n",
    "        for vec in special:\n",
    "            for a in range(vec[0], needs[0] + 1):\n",
    "                for b in range(vec[1], needs[1] + 1):\n",
    "                    for c in range(vec[2], needs[2] + 1):\n",
    "                        for d in range(vec[3], needs[3] + 1):\n",
    "                            for e in range(vec[4], needs[4] + 1):\n",
    "                                for f in range(vec[5], needs[5] + 1):\n",
    "                                    dp[a][b][c][d][e][f] = min(dp[a][b][c][d][e][f], dp[a - vec[0]][b - vec[1]][c - vec[2]][d - vec[3]][e - vec[4]][f - vec[5]] + vec[6])\n",
    "        return dp[-1][-1][-1][-1][-1][-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    # 用递归的方式，从最原始的needs开始，每次递归分为两组(全部单买/礼包购买)去找这个组合最便宜的价格\n",
    "        \n",
    "    def shoppingOffers(self, price: List[int], special: List[List[int]], needs: List[int]) -> int:\n",
    "        # 记录每个组合出现的最少钱数，key:value -> (A个数，B个数，C个数):累计价格\n",
    "        history = {}\n",
    "        \n",
    "        def _core(cur):\n",
    "            # 先算单个购买的价钱\n",
    "            val = sum([price[i]*cur[i] for i in range(len(cur))])\n",
    "            \n",
    "            # 循环测试大礼包\n",
    "            for sp in special: \n",
    "                # 如果使用该礼包，还有多少配额剩余\n",
    "                temp = [cur[i]-sp[i] for i in range(len(cur))]\n",
    "                \n",
    "                # 不能多买\n",
    "                if min(temp) >= 0:\n",
    "                    # val等于单买和用各种大礼包购买比较后的最小值\n",
    "                    val = min(val, history.get(tuple(temp), _core(temp))+sp[-1])\n",
    "                history[tuple(temp)] = val\n",
    "            \n",
    "            return val\n",
    "        \n",
    "        \n",
    "        return _core(needs)\n",
    "\n",
    "                \n",
    "            \n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shoppingOffers(self, price: List[int], special: List[List[int]], needs: List[int]) -> int:\n",
    "        d = dict()\n",
    "        def f(needs, special):\n",
    "            res = float('inf')\n",
    "            for i in range(len(needs)):\n",
    "                if special[i] != 0:\n",
    "                    res = min(res, needs[i] // special[i])\n",
    "            return res\n",
    "        def get_res(cnt, special, curr_needs):\n",
    "            needs = []\n",
    "            for i in range(len(curr_needs)):\n",
    "                needs.append(curr_needs[i] - cnt * special[i])\n",
    "            return needs\n",
    "        def get_state(curr_needs, start):\n",
    "            return (tuple(curr_needs), start)\n",
    "        def dfs(curr_needs, start):\n",
    "            if sum(curr_needs) == 0:\n",
    "                return 0\n",
    "            else:\n",
    "                tmp_state = get_state(curr_needs, start)\n",
    "                if tmp_state in d:\n",
    "                    return d[tmp_state]\n",
    "                else:\n",
    "                    if start < len(special):\n",
    "                        tmp_cnt = f(curr_needs, special[start])\n",
    "                        res = []\n",
    "                        for i in range(tmp_cnt + 1):\n",
    "                            tmp = dfs(get_res(i, special[start], curr_needs), start + 1)\n",
    "                            tmp += special[start][-1] * i\n",
    "                            res.append(tmp)\n",
    "                        res = min(res)\n",
    "                        d[tmp_state] = res\n",
    "                        return res\n",
    "                    else:\n",
    "                        tmp = 0\n",
    "                        for i, item in enumerate(curr_needs):\n",
    "                            tmp += item * price[i]\n",
    "                        res = tmp\n",
    "                        d[tmp_state] = tmp\n",
    "                        return tmp\n",
    "        return dfs(needs, 0)\n",
    "\n",
    "\n",
    "\n",
    "                    \n",
    "\n",
    "                 "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shoppingOffers(self, price: List[int], special: List[List[int]], needs: List[int]) -> int:\n",
    "        @lru_cache(None)\n",
    "        def dfs(i,state):\n",
    "            if i == len(special):\n",
    "                res = 0\n",
    "                for i in range(n):\n",
    "                    res += (needs[i] - state[i])*price[i] if needs[i] > state[i] else 0\n",
    "                return res\n",
    "            res = float('inf')\n",
    "            for num in range(51):\n",
    "                new_state = list(state)\n",
    "                label = True\n",
    "                for x in range(n):\n",
    "                    new_state[x] += special[i][x] * num\n",
    "                    if new_state[x] > needs[x]:\n",
    "                        label = False\n",
    "                        break\n",
    "                if label:\n",
    "                    res = min(dfs(i+1,tuple(new_state)) + special[i][-1] * num,res)\n",
    "            return res\n",
    "        n = len(price)\n",
    "        return dfs(0,tuple([0 for _ in range(n)]))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shoppingOffers(self, price: List[int], special: List[List[int]], needs: List[int]) -> int:\n",
    "        new_special = []\n",
    "        n = len(price)\n",
    "        for i in range(len(special)):\n",
    "            sums = 0\n",
    "            for j in range(n):\n",
    "                sums += special[i][j] * price[j] \n",
    "            if sums > special[i][n]:\n",
    "                new_special.append(special[i]) \n",
    "        m = len(new_special)\n",
    "        memo = dict()\n",
    "\n",
    "        def dfs(need, spec, i, cost):\n",
    "            if i == m:\n",
    "                sums = 0\n",
    "                for j in range(n):\n",
    "                    sums+=need[j] * price[j] \n",
    "                return cost + sums \n",
    "            t = tuple(need+[i,cost])\n",
    "            if t in memo:\n",
    "                return memo[t]\n",
    "            nxt_need = [0] * n \n",
    "            flag = 1\n",
    "            for j in range(n):\n",
    "                nxt_need[j] = need[j] - spec[i][j] \n",
    "                if nxt_need[j]< 0:\n",
    "                    flag = 0 \n",
    "            ans = float('inf')\n",
    "\n",
    "            if flag:\n",
    "                ans = min(ans, dfs(nxt_need, spec, i, cost+spec[i][n]))\n",
    "            ans = min(ans, dfs(need, spec, i+1, cost)) \n",
    "\n",
    "            memo[t] = ans\n",
    "            return memo[t]\n",
    "        \n",
    "        ans = dfs(needs, new_special, 0, 0)\n",
    "        return ans if ans < float('inf') else -1 \n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shoppingOffers(self, price: List[int], special: List[List[int]], needs: List[int]) -> int:\n",
    "        n = len(price)\n",
    "        valid_specials = []\n",
    "        q = [[0] * (n + 1)]\n",
    "        while len(q) > 0:\n",
    "            c = q.pop(0)\n",
    "            if not self.valid(c, needs):\n",
    "                continue \n",
    "            valid_specials.append(c)\n",
    "            for s in special:\n",
    "                q.append([c[i] + s[i] for i in range(n + 1)]) \n",
    "        lps = []\n",
    "        for c in valid_specials:\n",
    "            p = c[-1]\n",
    "            for i in range(n):\n",
    "                p += (needs[i] - c[i]) * price[i]\n",
    "            lps.append(p)\n",
    "        return min(lps) \n",
    "\n",
    "    def valid(self, c, needs):\n",
    "        for i, n in enumerate(needs):\n",
    "            if c[i] > n:\n",
    "                return False                \n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shoppingOffers(self, price: List[int], special: List[List[int]], needs: List[int]) -> int:\n",
    "        n = len(price)\n",
    "        valid_specials = []\n",
    "        q = [[0] * (n + 1)]\n",
    "        while len(q) > 0:\n",
    "            c = q.pop(0)\n",
    "            if not self.valid(c, needs):\n",
    "                continue \n",
    "            valid_specials.append(c)\n",
    "            for s in special:\n",
    "                q.append([c[i] + s[i] for i in range(n + 1)]) \n",
    "        lps = []\n",
    "        for c in valid_specials:\n",
    "            p = c[-1]\n",
    "            for i in range(n):\n",
    "                p += (needs[i] - c[i]) * price[i]\n",
    "            lps.append(p)\n",
    "        return min(lps) \n",
    "\n",
    "    def valid(self, c, needs):\n",
    "        for i, n in enumerate(needs):\n",
    "            if c[i] > n:\n",
    "                return False                \n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shoppingOffers(self, price: List[int], special: List[List[int]], needs: List[int]) -> int:\n",
    "        n = len(price)\n",
    "        f = lambda i: [f(i+1) for _ in range(needs[i]+1)] if i < n - 1 else [float('inf')]*(needs[i]+1)\n",
    "        combine = f(0)\n",
    "\n",
    "        def add_vec(v1, v2):\n",
    "            return [a + b for a, b in zip(v1, v2)]\n",
    "\n",
    "        def dfs(i, cur_vec, d_vec, p):\n",
    "            if i == n:\n",
    "                target_vec = add_vec(cur_vec, d_vec)\n",
    "                set_min_value(target_vec, p + get_value(cur_vec))\n",
    "                return\n",
    "\n",
    "            for k in range(needs[i]+1-d_vec[i]):\n",
    "                cur_vec[i] = k\n",
    "                dfs(i+1, cur_vec, d_vec, p)\n",
    "                \n",
    "        def get_value(vec):\n",
    "            c = combine\n",
    "            for i in vec:\n",
    "                c = c[i]\n",
    "            return c\n",
    "\n",
    "        def set_min_value(vec, value):\n",
    "            c = combine\n",
    "            for i in vec[:-1]:\n",
    "                c = c[i]\n",
    "            c[vec[-1]] = min(c[vec[-1]], value)\n",
    "\n",
    "\n",
    "        set_min_value([0]*n, 0)\n",
    "\n",
    "        for k, p in enumerate(price):\n",
    "            vec = [0]*n\n",
    "            vec[k] = 1\n",
    "            dfs(0, [0]*n, vec, p)\n",
    "\n",
    "\n",
    "        for s in special:\n",
    "            vec, p = s[:-1], s[-1]\n",
    "            dfs(0, [0]*n, vec, p)\n",
    "\n",
    "        return get_value(needs)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shoppingOffers(self, price: List[int], special: List[List[int]], needs: List[int]) -> int:\n",
    "        @cache\n",
    "        def dfs(idx, needs):\n",
    "            ret = sum([needs[i]*p for i, p in enumerate(price)])\n",
    "            if idx < n:\n",
    "                needs = list(needs)\n",
    "                flag = True\n",
    "                cost = 0\n",
    "                while flag:\n",
    "                    ret = min(ret, dfs(idx+1, tuple(needs))+cost)\n",
    "                    for i, s in enumerate(special[idx][:-1]):\n",
    "                        needs[i] -= s\n",
    "                        if needs[i] < 0:\n",
    "                            flag = False\n",
    "                            break\n",
    "                    cost += special[idx][-1]\n",
    "            return ret\n",
    "\n",
    "        cost = [0]\n",
    "        n = len(special)\n",
    "        return dfs(0, tuple(needs))\n",
    "         "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shoppingOffers(self, price: [int], special: [[int]], needs: [int]) -> int:\n",
    "        # # 方法一，记忆化递归，多维完全背包问题\n",
    "        # # f(i,needs)表示使用前i个礼包满足needs的最小价格\n",
    "        # # 考虑是否购买一个第i个礼包，可以将所有方案分为两类\n",
    "        # # 第一类是不购买第i个礼包，最小价格是f(i-1,needs)\n",
    "        # # 第二类是购买一个第i个礼包，最小价格是f(i,needs-special[i])+special[i][-1]，因为每个礼包可以的购买个数不受限制\n",
    "        # # 所以还可以再购买第i个礼包，所以考虑继续使用前i个礼包满足needs-special[i]，而不是前i-1个礼包\n",
    "        # n = len(price)  # 物品个数\n",
    "        # p = [[1 if j == i else 0 for j in range(n)] + [price[i]] for i in range(n)]  # 构建只有单个物品的礼包\n",
    "        # special = p + special\n",
    "        # memory = {(0,(0,)*n):0}\n",
    "        # def f(i,needs):  # 使用前i个礼包购买所有物品所需的最小价格\n",
    "        #     # 是否使用第i个礼包\n",
    "        #     if (i,needs) in memory:\n",
    "        #         return memory[(i,needs)]\n",
    "        #     if not any(needs) :\n",
    "        #         return 0\n",
    "        #     if i == 0:\n",
    "        #         memory[(i,needs)] = float('inf')\n",
    "        #         return float('inf')\n",
    "        #     res = f(i-1,tuple(needs))  # 不使用第i个礼包\n",
    "        #     new_needs = [0] * n\n",
    "        #     for j in range(n):\n",
    "        #         if special[i-1][j] > needs[j]:\n",
    "        #             memory[(i,needs)] = res\n",
    "        #             return res  # 第i个礼包超出了需要购买的物品\n",
    "        #         new_needs[j] = needs[j] - special[i-1][j]\n",
    "        #     memory[(i,needs)] = min(res,f(i,tuple(new_needs)) + special[i-1][n])\n",
    "        #     return memory[(i,needs)]\n",
    "        # return f(len(special),tuple(needs))\n",
    "\n",
    "\n",
    "#         # 方法二，显示地进行动态规划，超时了，因为每个状态都要计算一次，而记忆化递归不需要计算每个状态\n",
    "#         # dp[i][j][k][l][m][n][o]  # 因为最多六种物品，所以动态数组设置为1+6维\n",
    "#         n = len(price)\n",
    "#         needs += [0] * (6 - len(needs))  # 转换成6个物品的购买数量\n",
    "#         # print(needs)\n",
    "#         p = [[1 if j == i else 0 for j in range(n)] + [price[i]] for i in range(n)]  # 构建只有单个物品的礼包\n",
    "#         p = [item[:-1]+[0]*(6-n)+item[-1:] for item in p]\n",
    "#         special = [item[:-1]+[0]*(6-n)+item[-1:] for item in special]\n",
    "#         special = p + special\n",
    "#         # print(special)\n",
    "#         dp = [[[[[[[0 for o in range(needs[5] + 1)] for n in range(needs[4] + 1)] for m in range(needs[3] + 1)] for l in range(needs[2] + 1)] for k in range(needs[1] + 1)] for j in range(needs[0] + 1)] for i in range(len(special) + 1)]\n",
    "#         # 初始化\n",
    "#         dp[0] = [[[[[[float('inf') for o in range(needs[5] + 1)] for n in range(needs[4] + 1)] for m in range(needs[3] + 1)] for l in range(needs[2] + 1)] for k in range(needs[1] + 1)] for j in range(needs[0] + 1)]\n",
    "#         dp[0][0][0][0][0][0][0] = 0\n",
    "#         for i in range(1,len(special)+1):\n",
    "#             for j in range(0,needs[0] + 1):\n",
    "#                 for k in range(0,needs[1] + 1):\n",
    "#                     for l in range(0,needs[2] + 1):\n",
    "#                         for m in range(0,needs[3] + 1):\n",
    "#                             for n in range(0,needs[4] + 1):\n",
    "#                                 for o in range(0,needs[5] + 1):\n",
    "# #                                     print(i,j,k,l,m,n)\n",
    "#                                     if j < special[i-1][0]:\n",
    "# #                                         print(i,j,k,l,m,n)\n",
    "#                                         dp[i][j][k][l][m][n][o] = dp[i-1][j][k][l][m][n][o]\n",
    "#                                         continue\n",
    "#                                     if k < special[i-1][1]:\n",
    "#                                         dp[i][j][k][l][m][n][o] = dp[i-1][j][k][l][m][n][o]\n",
    "#                                         continue\n",
    "#                                     if l < special[i-1][2]:\n",
    "#                                         dp[i][j][k][l][m][n][o] = dp[i-1][j][k][l][m][n][o]\n",
    "#                                         continue\n",
    "#                                     if m < special[i-1][3]:\n",
    "#                                         dp[i][j][k][l][m][n][o] = dp[i-1][j][k][l][m][n][o]\n",
    "#                                         continue\n",
    "#                                     if n < special[i-1][4]:\n",
    "#                                         dp[i][j][k][l][m][n][o] = dp[i-1][j][k][l][m][n][o]\n",
    "#                                         continue\n",
    "#                                     if o < special[i-1][5]:\n",
    "#                                         dp[i][j][k][l][m][n][o] = dp[i-1][j][k][l][m][n][o]\n",
    "#                                         continue\n",
    "#                                     dp[i][j][k][l][m][n][o] = min(dp[i-1][j][k][l][m][n][o],dp[i][j-special[i-1][0]][k-special[i-1][1]][l-special[i-1][2]][m-special[i-1][3]][n-special[i-1][4]][o-special[i-1][5]] + special[i-1][6])\n",
    "#         return dp[-1][-1][-1][-1][-1][-1][-1]\n",
    "    \n",
    "# #         动态数组空间压缩，还是超时了\n",
    "#         # 显示地进行动态规划\n",
    "#         # dp[i][j][k][l][m][n][o]  # 因为最多六种物品，所以动态数组设置为1+6维\n",
    "#         n = len(price)\n",
    "#         needs += [0] * (6 - len(needs))  # 转换成6个物品的购买数量\n",
    "#         # print(needs)\n",
    "#         p = [[1 if j == i else 0 for j in range(n)] + [price[i]] for i in range(n)]  # 构建只有单个物品的礼包\n",
    "#         p = [item[:-1]+[0]*(6-n)+item[-1:] for item in p]\n",
    "#         special = [item[:-1]+[0]*(6-n)+item[-1:] for item in special]\n",
    "#         special = p + special\n",
    "#         # print(special)\n",
    "# #         dp = [[[[[[[0 for o in range(needs[5] + 1)] for n in range(needs[4] + 1)] for m in range(needs[3] + 1)] for l in range(needs[2] + 1)] for k in range(needs[1] + 1)] for j in range(needs[0] + 1)] for i in range(len(special) + 1)]\n",
    "#         # 初始化\n",
    "#         dp = [[[[[[float('inf') for o in range(needs[5] + 1)] for n in range(needs[4] + 1)] for m in range(needs[3] + 1)] for l in range(needs[2] + 1)] for k in range(needs[1] + 1)] for j in range(needs[0] + 1)]\n",
    "#         dp[0][0][0][0][0][0] = 0\n",
    "#         for i in range(1,len(special)+1):\n",
    "#             for j in range(0,needs[0] + 1):\n",
    "#                 for k in range(0,needs[1] + 1):\n",
    "#                     for l in range(0,needs[2] + 1):\n",
    "#                         for m in range(0,needs[3] + 1):\n",
    "#                             for n in range(0,needs[4] + 1):\n",
    "#                                 for o in range(0,needs[5] + 1):\n",
    "# #                                     print(i,j,k,l,m,n)\n",
    "#                                     if j < special[i-1][0]:\n",
    "#                                         dp[j][k][l][m][n][o] = dp[j][k][l][m][n][o]\n",
    "#                                         continue\n",
    "#                                     if k < special[i-1][1]:\n",
    "#                                         dp[j][k][l][m][n][o] = dp[j][k][l][m][n][o]\n",
    "#                                         continue\n",
    "#                                     if l < special[i-1][2]:\n",
    "#                                         dp[j][k][l][m][n][o] = dp[j][k][l][m][n][o]\n",
    "#                                         continue\n",
    "#                                     if m < special[i-1][3]:\n",
    "#                                         dp[j][k][l][m][n][o] = dp[j][k][l][m][n][o]\n",
    "#                                         continue\n",
    "#                                     if n < special[i-1][4]:\n",
    "#                                         dp[j][k][l][m][n][o] = dp[j][k][l][m][n][o]\n",
    "#                                         continue\n",
    "#                                     if o < special[i-1][5]:\n",
    "#                                         dp[j][k][l][m][n][o] = dp[j][k][l][m][n][o]\n",
    "#                                         continue\n",
    "#                                     dp[j][k][l][m][n][o] = min(dp[j][k][l][m][n][o],dp[j-special[i-1][0]][k-special[i-1][1]][l-special[i-1][2]][m-special[i-1][3]][n-special[i-1][4]][o-special[i-1][5]] + special[i-1][6])\n",
    "#         return dp[-1][-1][-1][-1][-1][-1]\n",
    "\n",
    "\n",
    "        # 继续优化，动态数组空间压缩，只计算更新礼包物品数量小于购买清单中对应物品数量的那些状态，通过\n",
    "        # 显示地进行动态规划\n",
    "        # dp[j][k][l][m][n][o]  # 因为最多六种物品，所以动态数组设置为6维\n",
    "        n = len(price)\n",
    "        needs += [0] * (6 - len(needs))  # 转换成6个物品的购买数量\n",
    "        p = [[1 if j == i else 0 for j in range(n)] + [price[i]] for i in range(n)]  # 构建只有单个物品的礼包\n",
    "        p = [item[:-1]+[0]*(6-n)+item[-1:] for item in p]\n",
    "        special = [item[:-1]+[0]*(6-n)+item[-1:] for item in special]\n",
    "        special = p + special\n",
    "        # 初始化\n",
    "        dp = [[[[[[float('inf') for o in range(needs[5] + 1)] for n in range(needs[4] + 1)] for m in range(needs[3] + 1)] for l in range(needs[2] + 1)] for k in range(needs[1] + 1)] for j in range(needs[0] + 1)]\n",
    "        dp[0][0][0][0][0][0] = 0\n",
    "        for i in range(1,len(special)+1):\n",
    "            for j in range(special[i-1][0],needs[0] + 1):\n",
    "                for k in range(special[i-1][1],needs[1] + 1):\n",
    "                    for l in range(special[i-1][2],needs[2] + 1):\n",
    "                        for m in range(special[i-1][3],needs[3] + 1):\n",
    "                            for n in range(special[i-1][4],needs[4] + 1):\n",
    "                                for o in range(special[i-1][5],needs[5] + 1):\n",
    "                                    dp[j][k][l][m][n][o] = min(dp[j][k][l][m][n][o],dp[j-special[i-1][0]][k-special[i-1][1]][l-special[i-1][2]][m-special[i-1][3]][n-special[i-1][4]][o-special[i-1][5]] + special[i-1][6])\n",
    "        return dp[-1][-1][-1][-1][-1][-1]\n",
    "\n",
    "        # # 多维动态规划，dp[i,j1,j2,j3]表示使用前i个大礼包刚好购买j1,j2,j3个物品A,B,C的最小花费\n",
    "        # # dp[i,j1,j2,j3] = min(dp[i,j1-k*i1,j2-k*i2,j3-k*i3]+k*i4)\n",
    "        # # 由于是多重，不好对子问题的先后顺序排序，所以使用记忆化递归\n",
    "        # # 记忆化递归，与上面的记忆化递归不同，这里是考虑满足needs的最后一次选择哪个礼包，上面考虑的是否选择第i个礼包\n",
    "        # n = len(price)  # 物品个数\n",
    "        # # 构建只具备单个物品的礼包\n",
    "        # p = [[1 if j == i else 0 for j in range(n)]+[price[i]] for i in range(n)]\n",
    "        # special = [sp for sp in special if self.bigger(needs,sp)]\n",
    "        # special = p + special\n",
    "        # memory = {(0,)*n: 0}\n",
    "        # for item in p:\n",
    "        #     memory[tuple(item[:n])] = item[n]\n",
    "        # for sp in special:\n",
    "        #     if tuple(sp[:n]) in memory:\n",
    "        #         if sp[n] < memory[tuple(sp[:n])]:\n",
    "        #             memory[tuple(sp[:n])] = sp[n]\n",
    "        # # needs = needs + [0] * (n - len(needs))\n",
    "        # def memory_recur(needs):\n",
    "            # if needs in memory:\n",
    "            #     return memory[needs]\n",
    "            # min_cost = float('inf')\n",
    "            # for sp in special[::-1]:\n",
    "            #     if sp[n] >= min_cost:\n",
    "            #         continue\n",
    "            #     isvalid = True\n",
    "            #     new_needs = []\n",
    "            #     for i in range(n):\n",
    "            #         if sp[i] > needs[i]:\n",
    "            #             isvalid = False\n",
    "            #             break\n",
    "    #                 new_needs.append(needs[i] - sp[i])\n",
    "    #             if not isvalid:\n",
    "    #                 continue\n",
    "    #             temp_res = memory_recur(tuple(new_needs))\n",
    "    #             if temp_res + sp[n] < min_cost:\n",
    "    #                 min_cost = temp_res + sp[n]\n",
    "    #         memory[needs] = min_cost\n",
    "    #         return min_cost\n",
    "    #     memory_recur(tuple(needs))\n",
    "    #     return memory[tuple(needs)]\n",
    "    # def bigger(self,a,b):\n",
    "    #     for i in range(len(a)):\n",
    "    #         if a[i] < b[i]:\n",
    "    #             return False\n",
    "    #     return True\n",
    "so = Solution() \n",
    "price = [2,5]\n",
    "special = [[3,0,5],[1,2,10]]\n",
    "needs = [3,2]\n",
    "so.shoppingOffers(price,special,needs)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shoppingOffers(self, price: List[int], special: List[List[int]], needs: List[int]) -> int:\n",
    "        @lru_cache(None)\n",
    "        def dfs(needs):\n",
    "            if min(needs)<0:\n",
    "                return math.inf\n",
    "            min_=sum([needs[i]*price[i] for i in range(len(price))])\n",
    "            for item in special:\n",
    "                min_=min(min_,item[-1]+dfs(tuple([needs[i]-item[i] for i in range(len(needs))])))\n",
    "            return min_\n",
    "        return dfs(tuple(needs))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shoppingOffers(self, price: List[int], special: List[List[int]], needs: List[int]) -> int:\n",
    "        weights = []\n",
    "        values = []\n",
    "        for l in special:\n",
    "            weights.append(l[:-1])\n",
    "            u=0\n",
    "            for i in range(len(price)):\n",
    "                u += price[i] * l[i]\n",
    "            values.append(u- l[-1])\n",
    "        \n",
    "        for i in range(len(values)-1, -1, -1):\n",
    "            if values[i] <=0:\n",
    "                values.pop(i)\n",
    "                weights.pop(i)\n",
    "\n",
    "        cost = sum([price[i] * needs[i] for i in range(len(needs))])\n",
    "        l = [11**i for i in range(len(weights))]\n",
    "        dpValue = dict()\n",
    "        dpValue[0] = 0\n",
    "        dpWeight = dict()\n",
    "        dpWeight[0] = needs[:]\n",
    "        queue = collections.deque([0])\n",
    "        maxValue = 0\n",
    "        while queue:\n",
    "            sol = queue.pop()\n",
    "            solNext = sol\n",
    "            for i in range(len(weights)):\n",
    "                solNext += l[i]\n",
    "                if not solNext in dpWeight:\n",
    "                    dpWeight[solNext] = dpWeight[sol][:]\n",
    "                    for j in range(len(needs)):\n",
    "                        dpWeight[solNext][j] -= weights[i][j]\n",
    "                    if min(dpWeight[solNext]) >= 0:\n",
    "                        dpValue[solNext] = dpValue[sol] + values[i]\n",
    "                        maxValue = max(maxValue, dpValue[solNext])\n",
    "                        queue.append(solNext)\n",
    "                solNext -= l[i]\n",
    "        return cost - maxValue"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\r\n",
    "class Solution:\r\n",
    "    def shoppingOffers(self, price: List[int], special: List[List[int]], needs: List[int]) -> int:\r\n",
    "        dp = [[[[[[float(\"inf\") for _ in range(7)]for _ in range(7)]for _ in range(7)]for _ in range(7)]for _ in range(7)]for _ in range(7)]\r\n",
    "        dp[0][0][0][0][0][0] = 0\r\n",
    "        needss = [0,0,0,0,0,0]\r\n",
    "        for i in range(len(needs)):\r\n",
    "            needss[i] = needs[i]\r\n",
    "        for i in range(len(price)):\r\n",
    "            a = [0]*len(special[0])\r\n",
    "            a[i] = 1\r\n",
    "            a[-1] = price[i]\r\n",
    "            special.append(a)\r\n",
    "        bu = 6 - len(special[0])+1\r\n",
    "        for i in range(len(special)):\r\n",
    "            special[i][:-1] += [0]*bu\r\n",
    "        # print(needss)\r\n",
    "        # print(special)\r\n",
    "        for i in range(len(special)):\r\n",
    "            for j0 in range(special[i][0],needss[0]+1):\r\n",
    "                for j1 in range(special[i][1], needss[1]+1):\r\n",
    "                    for j2 in range(special[i][2],needss[2]+1):\r\n",
    "                        for j3 in range(special[i][3],needss[3]+1):\r\n",
    "                            for j4 in range(special[i][4],needss[4]+1):\r\n",
    "                                for j5 in range(special[i][5],needss[5]+1):\r\n",
    "                                        dp[j0][j1][j2][j3][j4][j5] = min(\\\r\n",
    "                                            dp[j0-special[i][0]]\\\r\n",
    "                                                [j1-special[i][1]]\\\r\n",
    "                                                [j2-special[i][2]]\\\r\n",
    "                                                [j3-special[i][3]]\\\r\n",
    "                                                [j4-special[i][4]]\\\r\n",
    "                                                [j5-special[i][5]]+special[i][-1], dp[j0][j1][j2][j3][j4][j5])\r\n",
    "        return dp[needss[0]][needss[1]][needss[2]][needss[3]][needss[4]][needss[5]]\r\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shoppingOffers(self, price: List[int], special: List[List[int]], needs: List[int]) -> int:\n",
    "        types = len(price)\n",
    "        \n",
    "        if types==0:\n",
    "            return 0\n",
    "            \n",
    "            \n",
    "        length = len(special)\n",
    "\n",
    "        ans = [sum([price[i]*needs[i] for i in range(types)])]\n",
    "\n",
    "        import functools\n",
    "\n",
    "        @lru_cache(None)\n",
    "        def dfs(detail:tuple,payment:int):\n",
    "            \n",
    "            \n",
    "            for i in range(types):\n",
    "                if detail[i]<0:\n",
    "                    return\n",
    "\n",
    "            expay = payment\n",
    "            for i in range(types):\n",
    "                expay += price[i]*detail[i]\n",
    "            if ans[0]>expay:\n",
    "                ans[0] = expay\n",
    "\n",
    "            for i in range(length):\n",
    "                _temp = tuple()\n",
    "                for j in range(types):\n",
    "                    _temp+=(detail[j] - special[i][j],)\n",
    "                dfs(_temp,payment+special[i][-1])\n",
    "\n",
    "        dfs(tuple(needs),0)\n",
    "\n",
    "        return ans[0]\n",
    "                \n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def shoppingOffers(self, price: list[int], special: list[list[int]], needs: list[int]) -> int:\r\n",
    "        if max(needs) == 0: return 0\r\n",
    "        n = len(price)\r\n",
    "        m = 1 + math.floor(math.log2(max(needs)))\r\n",
    "        mk1 = (1 << m) - 1\r\n",
    "        mk2 = (1 << m * n) - 1\r\n",
    "        # setup m * n bit length target\r\n",
    "        target = 0\r\n",
    "        for i in range(n):\r\n",
    "            target |= needs[i] << (i * m)\r\n",
    "        # bitmask all valid specials\r\n",
    "        offers: dict[int, int] = dict()\r\n",
    "        for sp in special:\r\n",
    "            o = 0\r\n",
    "            p = 0\r\n",
    "            for i in range(n):\r\n",
    "                if sp[i] > needs[i]:\r\n",
    "                    o = -1\r\n",
    "                    break\r\n",
    "                o |= sp[i] << (i * m)\r\n",
    "                p += sp[i] * price[i]\r\n",
    "            if o >= 0 and sp[n] < p:\r\n",
    "                if o not in offers: offers[o] = p\r\n",
    "                offers[o] = min(offers[o], sp[n])\r\n",
    "        \r\n",
    "        # Dijkstra\r\n",
    "        cost = {0: 0, target: sum(p * x for p, x in zip(price, needs))}\r\n",
    "        hq = [(0, 0)]\r\n",
    "        heapq.heapify(hq)\r\n",
    "        while hq and hq[0][0] < cost[target]:\r\n",
    "            c, st = heapq.heappop(hq)\r\n",
    "            # buy 1 product of any\r\n",
    "            tmp = st\r\n",
    "            for i in range(n):\r\n",
    "                if (tmp & mk1) < needs[i]:\r\n",
    "                    nst = st & (mk2 ^ (mk1 << (i * m))) | (((tmp & mk1) + 1) << (i * m))\r\n",
    "                    if nst not in cost or cost[nst] > c + price[i]:\r\n",
    "                        cost[nst] = c + price[i]\r\n",
    "                        heapq.heappush(hq, (cost[nst], nst))\r\n",
    "                tmp >>= m\r\n",
    "            # buy 1 special offer of any\r\n",
    "            for o, p in offers.items():\r\n",
    "                nst = 0\r\n",
    "                tmp1 = st\r\n",
    "                tmp2 = o\r\n",
    "                for i in range(n):\r\n",
    "                    if tmp1 == 0 and tmp2 == 0: break\r\n",
    "                    if (tmp1 & mk1) + (tmp2 & mk1) > needs[i]:\r\n",
    "                        nst = -1\r\n",
    "                        break\r\n",
    "                    nst |= ((tmp1 & mk1) + (tmp2 & mk1)) << (i * m)\r\n",
    "                    tmp1 >>= m\r\n",
    "                    tmp2 >>= m\r\n",
    "                if nst >= 0 and (nst not in cost or cost[nst] > c + p):\r\n",
    "                    cost[nst] = c + p\r\n",
    "                    heapq.heappush(hq, (cost[nst], nst))\r\n",
    "        \r\n",
    "        return cost[target]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shoppingOffers(self, price: List[int], special: List[List[int]], needs: List[int]) -> int:\n",
    "        specialSelected = []\n",
    "        for sp in special:\n",
    "            pr = sum([p*n for p,n in zip(price, sp[:-1])])\n",
    "            if pr > sp[-1]:\n",
    "                specialSelected.append(sp)\n",
    "\n",
    "        dp = {}     # (i,j...): val\n",
    "        key_zero = tuple([0]*len(price))\n",
    "        dp[key_zero] = 0\n",
    "\n",
    "        def iter(key):\n",
    "            if key in dp:\n",
    "                return dp[key]\n",
    "            res = float('inf')\n",
    "            for sp in specialSelected:\n",
    "                pr = sp[-1]\n",
    "                \n",
    "                k = tuple([pr_key-pr_sp for pr_sp, pr_key in zip(sp[:-1], key)])\n",
    "                if min(k)>=0:\n",
    "                    res = min(res, pr + iter(k))\n",
    "\n",
    "            if res < float('inf'):\n",
    "                dp[key] = res\n",
    "                return res\n",
    "\n",
    "            for i, pr in enumerate(price):\n",
    "                if key[i]>0:\n",
    "                    k = list(key)\n",
    "                    k[i] -= 1\n",
    "                    k = tuple(k)\n",
    "                    res = min(res, pr + iter(k))\n",
    "            dp[key] = res\n",
    "            return res\n",
    "\n",
    "        return iter(tuple(needs))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shoppingOffers(self, price: List[int], special: List[List[int]], needs: List[int]) -> int:\n",
    "        @cache\n",
    "        def dfs(cost, need):\n",
    "            if cost >= ans[0]:\n",
    "                return None\n",
    "            if sum(need) == 0:\n",
    "                ans[0] = min(ans[0], cost)\n",
    "            f = 1\n",
    "            for pg in special:\n",
    "                tmp = list(need)\n",
    "                p = 1\n",
    "                for j in range(len(pg) - 1):\n",
    "                    tmp[j] -= pg[j]\n",
    "                    if tmp[j] < 0:\n",
    "                        p = 0\n",
    "                        break\n",
    "                if p:\n",
    "                    dfs(cost + pg[-1], tuple(tmp))\n",
    "                    f = 0\n",
    "            if f:\n",
    "                for i in range(len(price)):\n",
    "                    if need[i] >= 1:\n",
    "                        tmp = list(need)\n",
    "                        tmp[i] -= 1\n",
    "                        dfs(cost + price[i], tuple(tmp))\n",
    "        \n",
    "        l = len(needs)\n",
    "        ans = [0]\n",
    "        for i in range(l):\n",
    "            ans[0] += needs[i]*price[i]\n",
    "        res = tuple([0]*l)\n",
    "        for i in range(len(special) - 1, -1, -1):\n",
    "            tmp = 0\n",
    "            for j in range(len(special[i]) - 1):\n",
    "                tmp += special[i][j]*price[j]\n",
    "            if tmp <= special[i][-1]:\n",
    "                special.pop(i)\n",
    "        dfs(0, tuple(needs))\n",
    "        return ans[0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shoppingOffers(self, price: List[int], special: List[List[int]], needs: List[int]) -> int:\n",
    "        @cache\n",
    "        def dfs(cost, need):\n",
    "            if cost >= ans[0]:\n",
    "                return None\n",
    "            if need == res:\n",
    "                ans[0] = min(ans[0], cost)\n",
    "            f = 1\n",
    "            for pg in special:\n",
    "                tmp = list(need)\n",
    "                p = 1\n",
    "                for j in range(len(pg) - 1):\n",
    "                    tmp[j] -= pg[j]\n",
    "                    if tmp[j] < 0:\n",
    "                        p = 0\n",
    "                        break\n",
    "                if p:\n",
    "                    dfs(cost + pg[-1], tuple(tmp))\n",
    "                    f = 0\n",
    "            if f:\n",
    "                for i in range(len(price)):\n",
    "                    if need[i] >= 1:\n",
    "                        tmp = list(need)\n",
    "                        tmp[i] -= 1\n",
    "                        dfs(cost + price[i], tuple(tmp))\n",
    "        \n",
    "        l = len(needs)\n",
    "        ans = [0]\n",
    "        for i in range(l):\n",
    "            ans[0] += needs[i]*price[i]\n",
    "        res = tuple([0]*l)\n",
    "        for i in range(len(special) - 1, -1, -1):\n",
    "            tmp = 0\n",
    "            for j in range(len(special[i]) - 1):\n",
    "                tmp += special[i][j]*price[j]\n",
    "            if tmp <= special[i][-1]:\n",
    "                special.pop(i)\n",
    "        dfs(0, tuple(needs))\n",
    "        return ans[0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shoppingOffers(self, price: List[int], special: List[List[int]], needs: List[int]) -> int:\n",
    "        n = len(price)\n",
    "\n",
    "        from functools import lru_cache\n",
    "        @lru_cache(None)\n",
    "        def dfs(needs):\n",
    "            if any(val < 0 for val in needs):\n",
    "                return float('inf')\n",
    "            res = sum(price[i]*needs[i] for i in range(n))\n",
    "            for s in special:\n",
    "                nxneeds = [needs[i]-s[i] for i in range(n)]\n",
    "                cur = s[-1] + dfs(tuple(nxneeds))\n",
    "                res = min(res, cur)\n",
    "            return res\n",
    "\n",
    "        return dfs(tuple(needs))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from functools import lru_cache\n",
    "class Solution:\n",
    "    def shoppingOffers(self, price: List[int], special: List[List[int]], needs: List[int]) -> int:\n",
    "        @lru_cache(None)\n",
    "        def dfs(needs): \n",
    "            if min(needs) < 0:\n",
    "                return float('inf')\n",
    "            res = sum([price[i]*needs[i] for i in range(len(needs))])\n",
    "            for s in special:\n",
    "                res = min(res, dfs(tuple([needs[i]-s[i] for i in range(len(needs))])) + s[-1])\n",
    "            return res\n",
    "\n",
    "        return dfs(tuple(needs))\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shoppingOffers(self, price: List[int], special: List[List[int]], needs: List[int]) -> int:\n",
    "        # TO DO 删除没有优惠的special\n",
    "        n=len(price)\n",
    "        maxNeed = max(needs)+1\n",
    "        # newspecial=[]\n",
    "        # for s in special:\n",
    "        #     val, dele=0, False\n",
    "        #     for k in range(n):\n",
    "        #         val+=price[k]*s[k]\n",
    "        #         if s[k] > needs[k]:\n",
    "        #             dele = True\n",
    "        #             break\n",
    "        #     if dele: continue\n",
    "        #     if val < s[-1]: continue\n",
    "        #     if sum(s[:-1]) == 0: continue\n",
    "        #     newspecial.append(s)\n",
    "        newspecial=list(filter(lambda x:sum([price[k]*x[k] for k in range(n)])>x[-1] and sum(x[:-1]) > 0 and (not False in [x[k] <= needs[k] for k in range(n)]),special))\n",
    "\n",
    "        @functools.lru_cache(None)\n",
    "        def de(num):\n",
    "            ret=tuple([(num//maxNeed**i)%maxNeed for i in range(n)])\n",
    "            return ret\n",
    "\n",
    "        @functools.lru_cache(None)\n",
    "        def en(l):\n",
    "            num=0\n",
    "            for i in reversed(l):\n",
    "                num*=maxNeed\n",
    "                num+=i\n",
    "            return num\n",
    "\n",
    "        @functools.lru_cache(None)\n",
    "        def isok(sp,need):\n",
    "            sp=de(sp)\n",
    "            need=de(need)\n",
    "            for i in range(n):\n",
    "                if sp[i]>need[i]: return False\n",
    "            return True\n",
    "        \n",
    "        @functools.lru_cache(None)\n",
    "        def dp(cur):\n",
    "            if cur == 0: return 0\n",
    "            l=[]\n",
    "            for sp in newspecial:\n",
    "                if isok(en(tuple(sp[:-1])),cur):\n",
    "                    l.append(sp[-1]+dp(cur-en(tuple(sp[:-1]))))\n",
    "            if not l:\n",
    "                return sum([de(cur)[i]*price[i] for i in range(n)])\n",
    "            else:\n",
    "                return min(l)\n",
    "\n",
    "        return dp(en(tuple(needs)))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shoppingOffers(self, price: List[int], special: List[List[int]], needs: List[int]) -> int:\n",
    "        # TO DO 删除没有优惠的special\n",
    "        n=len(price)\n",
    "        maxNeed = max(needs)+1\n",
    "        newspecial=[]\n",
    "        for s in special:\n",
    "            val, dele=0, False\n",
    "            for k in range(n):\n",
    "                val+=price[k]*s[k]\n",
    "                if s[k] > needs[k]:\n",
    "                    dele = True\n",
    "                    break\n",
    "            if dele: continue\n",
    "            if val < s[-1]: continue\n",
    "            if sum(s[:-1]) == 0: continue\n",
    "            newspecial.append(s)\n",
    "\n",
    "        @functools.lru_cache(None)\n",
    "        def de(num):\n",
    "            ret=tuple([(num//maxNeed**i)%maxNeed for i in range(n)])\n",
    "            return ret\n",
    "\n",
    "        @functools.lru_cache(None)\n",
    "        def en(l):\n",
    "            num=0\n",
    "            for i in reversed(l):\n",
    "                num*=maxNeed\n",
    "                num+=i\n",
    "            return num\n",
    "\n",
    "        @functools.lru_cache(None)\n",
    "        def isok(sp,need):\n",
    "            sp=de(sp)\n",
    "            need=de(need)\n",
    "            for i in range(n):\n",
    "                if sp[i]>need[i]: return False\n",
    "            return True\n",
    "        \n",
    "        @functools.lru_cache(None)\n",
    "        def dp(cur):\n",
    "            if cur == 0: return 0\n",
    "            l=[]\n",
    "            for sp in newspecial:\n",
    "                if isok(en(tuple(sp[:-1])),cur):\n",
    "                    l.append(sp[-1]+dp(cur-en(tuple(sp[:-1]))))\n",
    "            if not l:\n",
    "                return sum([de(cur)[i]*price[i] for i in range(n)])\n",
    "            else:\n",
    "                return min(l)\n",
    "\n",
    "        return dp(en(tuple(needs)))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "def dotmul(a,b):\n",
    "    return sum([a[i]*b[i] for i in range(len(a))])\n",
    "def dotsub(a,b):\n",
    "    return [a[i]-b[i] for i in range(len(a))]\n",
    "def dotchk(a):\n",
    "    return any([c<0 for c in a])\n",
    "class Solution:\n",
    "    def shoppingOffers(self, price: List[int], special: List[List[int]], needs: List[int]) -> int:\n",
    "        n=len(needs)\n",
    "        @cache\n",
    "        def dp(t):\n",
    "            if dotchk(t):\n",
    "                return inf\n",
    "            ans=dotmul(price, t)\n",
    "            for sp in special:\n",
    "                ans=min(ans, sp[n]+dp(tuple(dotsub(t,sp[:n]))))\n",
    "            return ans\n",
    "        return dp(tuple(needs))\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "def dotmul(a,b):\n",
    "    return sum([a[i]*b[i] for i in range(len(a))])\n",
    "def dotsub(a,b):\n",
    "    return [a[i]-b[i] for i in range(len(a))]\n",
    "def dotchk(a):\n",
    "    return any([c<0 for c in a])\n",
    "class Solution:\n",
    "    def shoppingOffers(self, price: List[int], special: List[List[int]], needs: List[int]) -> int:\n",
    "        n=len(needs)\n",
    "        @cache\n",
    "        def dp(t):\n",
    "            if dotchk(t):\n",
    "                return inf\n",
    "            ans=dotmul(price, t)\n",
    "            for sp in special:\n",
    "                ans=min(ans, sp[n]+dp(tuple(dotsub(t,sp[:n]))))\n",
    "            return ans\n",
    "        return dp(tuple(needs))\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shoppingOffers(self, price: List[int], special: List[List[int]], needs: List[int]) -> int:\n",
    "        filtered = []\n",
    "        for s in special:\n",
    "            if any([a > b for a, b in zip(s, needs)]):\n",
    "                continue\n",
    "            if sum([a * b for a, b in zip(s, price)]) < s[-1]:\n",
    "                continue\n",
    "            filtered.append(s)\n",
    "        # print(len(special), len(filtered), filtered)\n",
    "        special = filtered\n",
    "        n = len(price)\n",
    "        slen = len(special)\n",
    "\n",
    "        \n",
    "        @cache\n",
    "        def dfs(needs):\n",
    "            if any([a < 0 for a in needs]):\n",
    "                return inf\n",
    "            ret = sum(p * i for p, i in zip(price, needs))\n",
    "            for i, sp in enumerate(special):\n",
    "                for need, offer in zip(needs, sp):\n",
    "                    if offer > need:\n",
    "                        break\n",
    "                ret = min(ret, sp[-1] + dfs(tuple([need - offer for need, offer in zip(needs, sp)])))\n",
    "            return ret\n",
    "        \n",
    "        return dfs(tuple(needs))\n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shoppingOffers(self, price: List[int], special: List[List[int]], needs: List[int]) -> int:\n",
    "        n = len(price)\n",
    "        valid_special = []\n",
    "        for sp in special:\n",
    "            pp = 0\n",
    "            for i in range(n):\n",
    "                pp += sp[i] * price[i]\n",
    "            if pp > sp[n]:\n",
    "                valid_special.append(sp)\n",
    "        @cache\n",
    "        def dp(cur_needs):\n",
    "            nonlocal n\n",
    "            cur_price = 0\n",
    "            for i in range(n):\n",
    "                if cur_needs[i] < 0:\n",
    "                    return float(\"inf\")\n",
    "                cur_price += cur_needs[i] * price[i]\n",
    "            for sp in valid_special:\n",
    "                cur_price = min(cur_price,dp(tuple([cur_needs[_] - sp[_] for _ in range(n)]))+sp[n])\n",
    "            return cur_price\n",
    "        return dp(tuple(needs))\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "from functools import lru_cache\n",
    "\n",
    "class Solution:\n",
    "    def shoppingOffers(self, price: List[int], special: List[List[int]], needs: List[int]) -> int:\n",
    "        ofr = len(special[0])\n",
    "\n",
    "        @lru_cache(None)\n",
    "        def dfs(need):\n",
    "            for i in need:\n",
    "                if i < 0:\n",
    "                    return float(\"inf\")\n",
    "\n",
    "            min1 = sum([i*j for i,j in zip(need,price)])   \n",
    "            if min1 == 0:\n",
    "                return 0            \n",
    "\n",
    "            min2 = min([dfs(tuple([need[i]-num for i,num in enumerate(s[:ofr-1])]))+s[-1] for s in special])\n",
    "            \n",
    "            return min(min1,min2)\n",
    "\n",
    "        return dfs(tuple(needs))\n",
    "\n",
    "\n",
    "                \n",
    "            \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "from functools import lru_cache\n",
    "\n",
    "class Solution:\n",
    "    def shoppingOffers(self, price: List[int], special: List[List[int]], needs: List[int]) -> int:\n",
    "        ofr = len(special[0])\n",
    "\n",
    "        @lru_cache(None)\n",
    "        def dfs(need):\n",
    "            min_ = min(need)\n",
    "            max_ = max(need)\n",
    "\n",
    "            if min_ < 0:\n",
    "                return float(\"inf\")\n",
    "\n",
    "            if min_ == 0 and max_ == 0:\n",
    "                return 0\n",
    "\n",
    "            min1 = min([dfs(tuple([need[i]-num for i,num in enumerate(s[:ofr-1])]))+s[-1] for s in special])\n",
    "            min2 = sum([i*j for i,j in zip(need,price)])\n",
    "            return min(min1,min2)\n",
    "\n",
    "        return dfs(tuple(needs))\n",
    "\n",
    "\n",
    "                \n",
    "            \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\r\n",
    "\r\n",
    "\r\n",
    "def dotmul(a, b):\r\n",
    "    return sum([a[i] * b[i] for i in range(len(a))])\r\n",
    "def dotsub(a, b):\r\n",
    "    return [a[i] - b[i] for i in range(len(a))]\r\n",
    "def dotchk(a):\r\n",
    "    return any([c < 0 for c in a])\r\n",
    "\r\n",
    "class Solution:\r\n",
    "    def shoppingOffers(self, price: List[int], special: List[List[int]], needs: List[int]) -> int:\r\n",
    "        # 记忆化搜索加剪枝\r\n",
    "        # self.res = float('inf')\r\n",
    "\r\n",
    "        # @cache\r\n",
    "        # def get_result(needs, s):\r\n",
    "        #     if s >= self.res:\r\n",
    "        #         return\r\n",
    "\r\n",
    "        #     flag = True\r\n",
    "        #     for i in range(len(needs)):\r\n",
    "        #         if needs[i] != 0:\r\n",
    "        #             flag = False\r\n",
    "        #             break\r\n",
    "        #     if flag:\r\n",
    "        #         self.res = min(self.res, s)\r\n",
    "        #         return\r\n",
    "\r\n",
    "        #     n = len(needs)\r\n",
    "        #     for val in special:\r\n",
    "        #         tmp = [0] * n\r\n",
    "        #         flag = True\r\n",
    "        #         for i in range(n):\r\n",
    "        #             if needs[i] - val[i] >= 0:\r\n",
    "        #                 tmp[i] = needs[i] - val[i]\r\n",
    "        #             else:\r\n",
    "        #                 flag = False\r\n",
    "        #                 break\r\n",
    "        #         if flag:\r\n",
    "        #             get_result(tuple(tmp), s + val[-1])\r\n",
    "\r\n",
    "        # n = len(needs)\r\n",
    "        # for i, v in enumerate(price):\r\n",
    "        #     tmp = [0] * (n + 1)\r\n",
    "        #     tmp[i] = 1\r\n",
    "        #     tmp[-1] = price[i]\r\n",
    "        #     special.append(tmp)\r\n",
    "\r\n",
    "        # get_result(tuple(needs), 0)\r\n",
    "        # return(self.res)\r\n",
    "\r\n",
    "        n = len(needs)\r\n",
    "        @cache\r\n",
    "        def dp(t):\r\n",
    "            if dotchk(t):\r\n",
    "                return(float('inf'))\r\n",
    "            ans = dotmul(price, t)\r\n",
    "            for sp in special:\r\n",
    "                ans = min(ans, sp[n] + dp(tuple(dotsub(t, sp[:n]))))\r\n",
    "            return ans\r\n",
    "        return(dp(tuple(needs)))\r\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\r\n",
    "\r\n",
    "\r\n",
    "def dotmul(a, b):\r\n",
    "    return sum([a[i] * b[i] for i in range(len(a))])\r\n",
    "def dotsub(a, b):\r\n",
    "    return [a[i] - b[i] for i in range(len(a))]\r\n",
    "def dotchk(a):\r\n",
    "    return any([c < 0 for c in a])\r\n",
    "\r\n",
    "class Solution:\r\n",
    "    def shoppingOffers(self, price: List[int], special: List[List[int]], needs: List[int]) -> int:\r\n",
    "        # 记忆化搜索加剪枝\r\n",
    "        # self.res = float('inf')\r\n",
    "\r\n",
    "        # @cache\r\n",
    "        # def get_result(needs, s):\r\n",
    "        #     if s >= self.res:\r\n",
    "        #         return\r\n",
    "\r\n",
    "        #     flag = True\r\n",
    "        #     for i in range(len(needs)):\r\n",
    "        #         if needs[i] != 0:\r\n",
    "        #             flag = False\r\n",
    "        #             break\r\n",
    "        #     if flag:\r\n",
    "        #         self.res = min(self.res, s)\r\n",
    "        #         return\r\n",
    "\r\n",
    "        #     n = len(needs)\r\n",
    "        #     for val in special:\r\n",
    "        #         tmp = [0] * n\r\n",
    "        #         flag = True\r\n",
    "        #         for i in range(n):\r\n",
    "        #             if needs[i] - val[i] >= 0:\r\n",
    "        #                 tmp[i] = needs[i] - val[i]\r\n",
    "        #             else:\r\n",
    "        #                 flag = False\r\n",
    "        #                 break\r\n",
    "        #         if flag:\r\n",
    "        #             get_result(tuple(tmp), s + val[-1])\r\n",
    "\r\n",
    "        # n = len(needs)\r\n",
    "        # for i, v in enumerate(price):\r\n",
    "        #     tmp = [0] * (n + 1)\r\n",
    "        #     tmp[i] = 1\r\n",
    "        #     tmp[-1] = price[i]\r\n",
    "        #     special.append(tmp)\r\n",
    "\r\n",
    "        # get_result(tuple(needs), 0)\r\n",
    "        # return(self.res)\r\n",
    "\r\n",
    "        n = len(needs)\r\n",
    "        @cache\r\n",
    "        def dp(t):\r\n",
    "            if dotchk(t):\r\n",
    "                return(float('inf'))\r\n",
    "            ans = dotmul(price, t)\r\n",
    "            for sp in special:\r\n",
    "                ans = min(ans, sp[n] + dp(tuple(dotsub(t, sp[:n]))))\r\n",
    "            return ans\r\n",
    "        return(dp(tuple(needs)))\r\n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
